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 compendium 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. This article
presents curricular materials, based on original 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''(*Das Entscheidungsproblem* is German
for *the decision problem*) [T],
a paper which outlines a logical
device (a ``Turing Machine''), that is the forerunner of a modern
computer program.

The two projects included in this article, ``An Introduction to Turing Machines'' (pdf file) (ps file), and ``Turing Machines, Induction and Recursion'' (pdf file) (ps file), were both assigned recently in a beginning discrete mathematics course at New Mexico State University, and build on the pedagogical idea of calculus projects [CG]. 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. Each project contributed significantly towards the student's course grade (about 25% per project), and each took the place of an in-class examination. Student reaction was overwhelmingly positive, with most becoming actively involved in both the historical significance of the piece as well as the details of the solutions to particular questions. Several students excelled beyond the specifics of the project, researched independently the impact of Turing's work, and discussed this in their papers. Particular advantages of the written historical project include providing context and direction to the subject matter, honing the students' verbal and deductive skills through reading the original work of some of the greatest minds in history, and the rediscovery of the roots common to discrete mathematics and computer science.

David Hilbert (1862--1943), an intellectual giant of the last century, is well known for his list of mathematical problems in 1900 [H1, pp. 290--329] [HN], whose study and (attempted) solutions would occupy many mathematicians for at least another hundred years. Among the problems were the foundational questions of whether the axioms of arithmetic are consistent, and whether there is a number system in cardinality between the rational numbers and the continuum of real numbers. In 1928 Hilbert posed another group of problems [H2, HA1] this time dealing with the consistency, completeness and independence of the axioms of a logical system in general, as well as the problem of deciding whether a given statement is valid within a logical system. The solutions to these problems, in particular Kurt Gödel's (1906--1978) demonstration of the incompleteness of arithmetic with the existence of statements that are not provable (as true or false) [Go], had profound consequences for mathematics, and brought to the fore mathematical logic as a separate field of study [Gr]. In this article, however, we deal primarily with the decision problem, which, to quote Hilbert and Ackermann [HA2, pp. 112--113], can be stated as:

. . . there emerges the fundamental importance of determining whether or not a given formula of the predicate calculus is universally valid. . . . A formula . . . is calledsatisfiableif the sentential variables can be replaced with the values truth and falsehood . . . in such a way that the formula [becomes] a true sentence. . . . It is customary to refer to the equivalent problems ofuniversal validityandsatisfiabilityby the common name of thedecision problem.

Following Gödel's results, the decision problem remained, although
it must be reinterpreted as meaning whether there is a procedure
by which a given proposition can be determined to be
either ``provable'' or ``unprovable''. In the text *Introduction
to Mathematical Logic* [C3, p. 99 ],
Alonzo Church (1903--1995) formulated this problem as:
``*The decision problem* of a logistic system is the problem to
find an effective procedure or algorithm, a *decision procedure*,
by which for an arbitrary well-formed formula of the system, it is
possible to determine whether or not it is a theorem . . . .''
To be sure, Church proves that the decision problem has no solution
[C1,
C2],
although it is the algorithmic character of Turing's
solution that is pivotal to the logical underpinnings of the
programmable computer. Moreover, the simplicity of a Turing machine
provides a degree of accessibility to the subject ideal for a first
course in logic or discrete mathematics.

Briefly a Turing machine, *M*, is a device which prints a
sequence of zeroes and ones on a tape based on (i) the figure
currently being scanned on the tape, and (ii) a set of instructions.
Moreover, Turing describes the logical construction of a universal
computing machine, *U*, which accepts the set of instructions of
a given machine *M* in some standard form, and then outputs the same
sequence as *M*. Applying a machine *U* to another
machine *M* is
denoted as *U(M)* for this exposition. It follows from
Turing's paper [T]
that if the decision problem has a solution,
then there is a machine *D* which accepts the set of instructions of
another machine *M* and decides whether *M*
prints a finite or an infinite number of symbols on the tape.
Determining whether a machine terminates in a finite number of
executable steps is today known as the halting problem in computer
science. If the decision problem, and hence the halting problem has a
solution, then a new machine *T* can be defined so that
*T(M)* halts if *M* does not halt, and
*T(M)* does not halt if *M* halts. By considering
the behavior of *T(T)*, we conclude that *T* halts
and *T* does not halt, a contradiction, from which it follows
that the decision problem has no solution.

What follows are descriptions and the actual text of the projects ``An Introduction to Turing Machines'' (pdf file) (ps file) and ``Turing Machines, Induction and Recursion'' (pdf file) (ps file), along with a few words of advice for the instructor. The first project acquaints students with the workings of a Turing machine, asks the reader to compute the output of a particular machine, and then to design a machine with a given output. All background needed to answer these questions is gleaned from reading the excerpts from Turing's original paper included in the project, without a special in-class lecture to define a Turing machine. In fact, an entire class session was set aside to allow the students to work on their project and discuss their progress among themselves. During office hours or while students worked during class, I would answer questions about the output of the examples presented in Turing's paper, but only on the students' initiative. The project also asks the students to design a Turing machine to test the property of set containment (for finite sets), which builds on the topic of set theory, covered just prior to the assignment of the project. For that question, the operation of storing a character in memory is allowed, although Turing did not include this feature in his paper. The instructor is encouraged to tailor the projects to mesh with what has transpired in class, add some questions relevant to topics being covered, and delete or rephrase others. The details of a project should be clear before assignment.

The second project, ``Turing Machines, Induction and Recursion''
(pdf file)
(ps file),
explores the machine's capacity for a limited type of memory, and its use
in elementary arithmetic operations. In particular, the students are
asked to describe a machine, which given two positive integers `n`
and `m`, produces the product
`n` `x` `m`. In doing so, the student
witnesses the appearance of recursion when repeating steps in a Turing
machine as well as the use of induction
when verifying that the output of a machine is the
desired result. For the second project, the students worked in groups
of two or three, which often resulted in a group dynamic with one
member proposing an algorithm for multiplication, and the other group
members testing its accuracy. The first project, on the other hand,
was an individual project, requiring that every student learn the
rudiments of a Turing machine before tackling the more sophisticated
concepts of induction and recursion needed for the design features
of the second project. The second highlights the need of several
abstract topics in discrete mathematics for programming needs.

Two projects appear to be ample material for a one-semester course, supplemented with a midterm and final, both of which could include questions about the projects. Two additional projects have been crafted from Turing's paper. The third in this sequence (pdf file) (ps file) outlines the development Turing's idea of a universal computing machine (today known as a compiler or an interpreter), while the fourth (pdf file) (ps file) describes Turing's negative solution to the decision problem in what has become known as the halting problem in computer science. These last two projects would be best suited for an intermediate or advanced undergraduate course in the subject. Finally, for a detailed history of related topics in logic, see [Gr]; for a leisurely account of the events leading up to the programmable computer, see [Da]; and for a detailed description of Turing's life and times, see [Ho].

The written historical projects in this article combine learning techniques from both a projects-based approach to instruction [CG] and an historically informed teaching strategy [Sw]. For implementation in the classroom, introduction to the relevant historical material should begin early in the course, with a brief description of Hilbert's problem list, its effect on the development of mathematics, and the significance of the decision problem. Further commentary about the evolution of Turing's ideas into the modern programmable computer should be provided by the instructor before assigning the projects. If the projects are used verbatim, allow about two weeks for the completion of each. Monitor the students' progress on what for them is a lengthy assignment, provide in-class time for them to work on the projects, and offer guidance when they (and they will) become perplexed. The projects should count for a significant percentage of the course grade, with each taking the place of an in-class examination, thus providing incentive to complete them. Modify the projects to fit the course, with the course content and class size being factors which may well influence the questions asked. For example, if set containment has not been covered, this part of Project I (part(e)) may be deleted, or for a large class, deleting part (e) would much simplify project, and reduce the time needed for grading. Project II could be shortened by asking the students to design a Turing machine to compute the sum of two positive integers, instead of the product. Nonetheless, pedagogical advantages are to be had by asking significant questions, ones which engage the students and reflect the actual development of the subject.

The author gratefully acknowledges permission from the London Mathematical Society to reproduce excerpts from Alan Turing's paper ``On Computable Numbers with an Application to the Entscheidungsproblem,'' [T]. The development of curricular materials for discrete mathematics has been partially supported by the National Science Foundation's Course, Curriculum and Laboratory Improvement Program under grant DUE-0231113, for which the author is most appreciative.

[C1]
Church, A., ``An Unsolvable Problem of Elementary Number
Theory,'' *American Journal of Math.* **58** (1936)
345--363.

[C2]
Church, A., ``A Note on the Entscheidungsproblem,'' *
Journal of Symbolic Logic* **1** (1936) 40--41.

[C3]
Church, A., *Introduction to Mathematical Logic*,
Princeton University Press, Princeton, New Jersey, 1996.

[CG]
Cohen, M., Gaughan, E., Knoebel, A., Kurtz, D., Pengelley, D.,
*Student Research Projects in Calculus*, Mathematical Association
of America, Washington D.C., 1992.

[Da]
Davis, M., *The Universal Computer*, W. W. Norton
& Co., New York, 2000.

[Go]
Gödel, K., ``Über Formal Unentscheidbare Sätze
der Principia Mathematica und Verwandter Systeme,'' *Monatshefte
für Mathematik und Physik* **38** (1931) 173--198. (English
translation in *The Undecidable*, M. Davis, editor, Raven Press, New
York, 1965.)

[Gr]
Grattan-Guinness, I., * The Search for
Mathematical Roots, 1870--1940: Logics, Set Theories and The
Foundations of Mathematics from Cantor through Russell to Gödel*,
Princeton University Press, Princeton, 2000.

[H1]
Hilbert, D., *Gesammelte Abhandlungen*, Vol. III,
Chelsea Publishing Co., New York, 1965.

[HN]
Hilbert, D., Mathematical Problems, Newson M.,
translator, *Bulletin of the American Mathematical Society*
**8** (1902) 437--439.

[H2]
Hilbert, D., ``Probleme der Grundlegung der Mathematik,''
*Mathematische Annalen* **102** (1930) 1--9.

[HA1]
Hilbert, D., Ackermann, W., *Grundzüge der
Theoretischen Logik*, Dover Publications, New York, 1946.

[HA2]
Hilbert, D., Ackermann, W., *Principles of
Mathematical Logic*, Hammond, L., Leckie, G., Steinhardt, F.,
translators, Chelsea Publishing Co., New York, 1950.

[Ho]
Hodges, A., *Alan Turing: The Enigma*, Simon &
Schuster, Inc., New York, 1983. *Breaking the Code*, video available
at www.wgbh.org/shop/

[Sw]
Swetz, F., Fauvel, J., Bekken, O., Johansson, B.,
Katz, V., editors, *Learn From The Masters*, Mathematical
Association of America, Washington, D.C., 1995.

[T] Turing, A.,
``On Computable Numbers with an Application
to the Entscheidungsproblem,'' * Proceedings of the London
Mathematical Society* ** 42 ** (1936) 230--265.

Return to top of page