# Introducing Logic via Turing Machines

Jerry Lodder; Mathematical Sciences MSC-3MB; Box 30001; New Mexico State University; Las Cruces, NM 88003

### A Curious Situation

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.

### The Decision Problem

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 called satisfiable if 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 of universal validity and satisfiability by the common name of the decision 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.

### The Projects

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].

### ACKNOWLEDGMENT

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.

### Bibliography

[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.