Introduction to Turing Machines

Jing-Chao Chen

Bell Labs Research China, Lucent Technologies, Bejing

Yatsuka Nakamura

Shinshu University, Nagano

Summary.

A Turing machine can be viewed as a simple kind of computer, whose operations are constrainted to reading and writing symbols on a tape, or moving along the tape to the left or right. In theory, one has proven that the computability of Turing machines is equivalent to recursive functions. This article defines and verifies the Turing machines of summation and three primitive functions which are successor, zero and project functions. It is difficult to compute sophisticated functions by simple Turing machines. Therefore, we define the combination of two Turing machines.

MML Identifier: TURING_1

Contents (PDF format)

1. Preliminaries
2. Definitions and Terminology for Turing Machine
3. Summation of Two Natural Numbers
4. Computing Successor Function
5. Computing Zero Function
6. Computing $n$-ary Project Function
7. Combining Two Turing Machines into One

Bibliography

[1] Grzegorz Bancerek. The fundamental properties of natural numbers. Journal of Formalized Mathematics, 1, 1989.

[2] Grzegorz Bancerek. The ordinal numbers. Journal of Formalized Mathematics, 1, 1989.

[3] Grzegorz Bancerek. Sequences of ordinal numbers. Journal of Formalized Mathematics, 1, 1989.

[4] Grzegorz Bancerek and Krzysztof Hryniewiecki. Segments of natural numbers and finite sequences. Journal of Formalized Mathematics, 1, 1989.

[5] Grzegorz Bancerek and Piotr Rudnicki. The set of primitive recursive functions. Journal of Formalized Mathematics, 13, 2001.

[6] Czeslaw Bylinski. Functions and their basic properties. Journal of Formalized Mathematics, 1, 1989.

[7] Czeslaw Bylinski. Functions from a set to a set. Journal of Formalized Mathematics, 1, 1989.

[8] Czeslaw Bylinski. Partial functions. Journal of Formalized Mathematics, 1, 1989.

[9] Czeslaw Bylinski. Some basic properties of sets. Journal of Formalized Mathematics, 1, 1989.

[10] Czeslaw Bylinski. A classical first order language. Journal of Formalized Mathematics, 2, 1990.

[11] Czeslaw Bylinski. Finite sequences and tuples of elements of a non-empty sets. Journal of Formalized Mathematics, 2, 1990.

[12] Czeslaw Bylinski. The modification of a function by a function and the iteration of the composition of a function. Journal of Formalized Mathematics, 2, 1990.

[13] Jing-Chao Chen. A small computer model with push-down stack. Journal of Formalized Mathematics, 11, 1999.

[14] Agata Darmochwal. Finite sets. Journal of Formalized Mathematics, 1, 1989.

[15] Krzysztof Hryniewiecki. Basic properties of real numbers. Journal of Formalized Mathematics, 1, 1989.

[16] Dariusz Surowik. Cyclic groups and some of their properties --- part I. Journal of Formalized Mathematics, 3, 1991.

[17] Andrzej Trybulec. Domains and their Cartesian products. Journal of Formalized Mathematics, 1, 1989.

[18] Andrzej Trybulec. Tarski Grothendieck set theory. Journal of Formalized Mathematics, Axiomatics, 1989.

[19] Andrzej Trybulec. Tuples, projections and Cartesian products. Journal of Formalized Mathematics, 1, 1989.

[20] Andrzej Trybulec. Function domains and Fr\aenkel operator. Journal of Formalized Mathematics, 2, 1990.

[21] Andrzej Trybulec. Subsets of real numbers. Journal of Formalized Mathematics, Addenda, 2003.

[22] Michal J. Trybulec. Integers. Journal of Formalized Mathematics, 2, 1990.

[23] Wojciech A. Trybulec. Pigeon hole principle. Journal of Formalized Mathematics, 2, 1990.

[24] Zinaida Trybulec. Properties of subsets. Journal of Formalized Mathematics, 1, 1989.

[25] Edmund Woronowicz. Relations and their basic properties. Journal of Formalized Mathematics, 1, 1989.