Introduction

A curious situation has arisen today in the undergraduate curriculum with many computer science majors learning the fundamentals of logic from a memorized list of truth tables and rules of inference, without regard to the original problems whose solutions involved the logic that would become part of the programmable computer. Current discrete mathematics textbooks, which often cover combinatorics, deductive reasoning and predicate logic, present the material as a fast-paced news reel of facts and formulae, with only passing mention of the original work and pioneering solutions that eventually found resolution through the modern concepts of induction, recursion and algorithm. Presented here are curricular materials, based on primary historical sources, designed for use in an introductory discrete mathematics course, particularly one with a significant number of computer science majors. The materials are organized into two-week written projects for students, and offer excerpts from Alan Turing's (1912–1954) original 1936 paper “On Computable Numbers with an Application to the Entscheidungsproblem” [49], a paper which outlines a logical device, a Turing Machine, that is the forerunner of a modern computer program.

The two projects included here, “An Introduction to Turing Machines” and “Turing Machines, Induction and Recursion,” were both assigned recently in a beginning discrete mathematics course at New Mexico State University, and build on the pedagogical idea of calculus projects [5]. For each project the students wrote a detailed paper, answering a sequence of guided questions designed to illuminate the ground-breaking ideas of Turing's work.