Activity 9: An Introduction to Turing Machines
HPS391 Rebels who Count: History of Mathematics Since 1700
MAT391 History of Mathematics since 1700
Winter 2021, Instructor: Sylvia Nickerson
Maximum points: 38/38
1 Introduction to Turing Machines
During the International Congress of Mathematicians in Paris in 1900 David
Hilbert (1862–1943), one of the leading mathematicians of the last century,
proposed a list of problems for the following generations to ponder. On the
list was whether the axioms of arithmetic are consistent, a question which
would have profound consequences for the foundations of mathematics. Con-
tinuing in this direction, in 1928 Hilbert proposed the decision problem (das
Entscheidungsproblem), which asked whether there was a standard proce-
dure that can be applied to decide whether a given mathematical state-
ment is true. In a revolutionary paper “On Computable Numbers, with an
Application to the Entscheidungsproblem” published in 1936, Alan Turing
(1912–1954) proved that the decision problem had no solution, and in doing
so he outlined the rudimentary ideas which form the basis for the mod-
ern programmable computer. Today his construction is known as a Turing
machine.
The goal of this project is to read a few excerpts from Turing’s original
paper1 and understand how to read and write simple instructions for a
Turing Machine. After carefully reading the attached pages, answer the
following:
(Task 1) Describe the workings of a Turing machine (referred to as a “com-
puting machine” in the original paper). [5 points]
(Task 2) What is the precise output of the machine in Example 1. In
your answer draw the output on the tape, as well as the binary decimal
1Turing, A.M., “On Computable Numbers with an Application to the Entschei-
dungsproblem,” Proceedings of the London Mathematical Society, 42 (1936), pp. 230–265.
1
represented and its precise real number equivalent. [6 points]
(Task 3) Design a Turing machine which generates the following output.
Be sure to justify your answer. [6 points]
010010100101001 . . .
(Task 4) Describe the behavior of the following machine, which begins with
a blank tape, with the machine in configuration α. [4 points]
Configuration Behavior
m-config. symbol operation final m-config.
α none R P1 β
α 1 R P0 β
α 0 HALT (none)
β 1 R P1 α
β 0 R P0 α
ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO
THE ENTSCHEIDUNGSPROBLEM
By A. M. Turing.
1. Computing Machines.
We have said that the computable numbers are those whose decimals are
calculable by finite means. This requires more explicit definition. No real at-
tempt will be made to justify the definitions given until we reach §9. For present
I shall only say that the justification lies in the fact that the human memory is
necessarily limited.
We may compare a man in the process of computing a real number to a
machine which is only capable of a finite number of conditions q1, q2, . . ., qR,
which will be called the “m-configurations”. The machine is supplied with a
“tape” (the analogue of paper) running through it, and divided into sections
(called “squares”) each capable of bearing a “symbol”. At any moment there
is just one square, say the r-th, bearing the symbol S(r) which is “in the
machine”. We may call this square the “scanned square”. The symbol on the
scanned square may be called the “scanned symbol”. The “scanned symbol” is
the only one of which the machine is, so to speak, “directly aware”. However,
by altering its m-configuration the machine can effectively remember some of
the symbols it has “seen” (scanned) previously. The possible behaviour of
the machine at any moment is determined by the m-configuration qn and the
2
scanned symbol S(r). This pair qn, S(r) will be called the “configuration”;
thus the configuration determines the possible behaviour of the machine. In
some of the configurations in which the scanned square is blank (i.e. bears no
symbol) the machine writes down a new symbol on the scanned square; in other
configurations it erases the scanned symbol. The machine may also change the
square which is being scanned, but only by shifting it one place to right or left.
In addition to any of these operations the m-configuration may be changed.
Some of the symbols written down will form the sequence of figures which is
the decimal of the real number which is being computed. The others are just
rough notes to “assist the memory”. It will only be these rough notes which
will be liable to erasure.
It my contention that these operations include all those which are used in
the computation of a number. The defense of this contention will be easier
when the theory of the machines is familiar to the reader. In the next section
I therefore proceed with the development of the theory and assume that it is
understood what is meant by “machine”, “tape”, “scanned”, etc.
2. Definitions.
Automatic machines.
If at each stage the motion of a machine (in the sense of §1)is completely
determined by the configuration, we shall call the machine an “automatic ma-
chine” (or a-machine).
For some purposes we might use machines (choice machines or c-machines)
whose motion is only partially determined by the configuration (hence the use of
the word “possible” in §1). When such a machine reaches one of these ambigu-
ous configurations, it cannot go on until some arbitrary choice has been made
by an external operator. This would be the case if we were using machines to
deal with axiomatic systems. In this paper I deal only with automatic machines,
and will therefore often omit the prefix a-.
Computing machines.
If an a-machine prints two kinds of symbols, of which the first kind (called
figures) consists entirely of 0 and 1 (the others being called symbols of the
second kind), then the machine will be called a computing machine. If the
machine is supplied with a blank tape and set in motion, starting from the
correct initial m-configuration the subsequence of the symbols printed by it
which are of the first kind will be called the sequence computed by the machine.
The real number whose expression as a binary decimal is obtained by prefacing
this sequence by a decimal point is called the number printed by the machine.
At any stage of the motion of the machine, the number of the scanned
3
square, the complete sequence of all symbols on the tape, and them-configuration
will be said to describe the complete configuration at that stage. The changes
of the machine and tape between successive complete configurations will be
called the moves of the machine.
3. Examples of computing machines.
I. A machine can be constructed to compute the sequence 010101 . . .. The
machine is to have the four m-configurations “b”, “c”, “f”, “e” and is capable
of printing “0” and “1”. The behaviour of the machine is described in the
following table in which “R” means “the machine moves so that it scans the
square immediately on the right of the one it was scanning previously”. Similarly
for “L”. “E” means “the scanned symbol is erased and “P” stands for “prints”.
This table (and all succeeding tables of the same kind) is to be understood to
mean that for a configuration described in the first two columns the operations
in the third column are carried out successively, and the machine then goes
over into the m-configuration described in the last column. When the second
column is blank, it is understood that the behaviour of the third and fourth
columns applies for any symbol and for no symbol. The machine starts in the
m-configuration b with a blank tape. (Example 1).
Configuration Behaviour
m-config. symbol operation final m-config.
b none P0, R c
c none R e
e none P1, R f
f none R b
If (contrary to the description §1) we allow the letters L, R to appear more
than once in the operations column we can simplify the table considerably.
Configuration Behaviour
m-config. symbol operation final m-config.
b none P0 b
b 0 R, R, P1 b
b 1 R, R, P0 b
2 Turing Machines: Induction and Recursion
The logic behind the modern programmable computer owes much to Turing’s
“computing machines,” discussed in the first section. Since the state of the
4
machine, or m-configuration as called by Turing, can be altered according
to the symbol being scanned, the operation of the machine can be changed
depending on what symbols have been written on the tape, and affords
the machine a degree of programmability. The program consists of the list
of configurations of the machine and its behavior for each configuration.
Turing’s description of his machine, however, did not include memory in
its modern usage for computers, and symbols read on the tape could not
be stored in any separate devise. Using a brilliant design feature for the
tape, Turing achieves a limited type of memory for the machine, which
allows it to compute many arithmetic operations. The numbers needed for
a calculation are printed on every other square of the tape, while the squares
between these are used as “rough notes to ‘assist the memory.’ It will only
be these rough notes which will be liable to erasure” [1, p. 232].
Turing continues: The convention of writing the figures only on alternate
squares is very useful: I shall always make use of it. I shall call the one se-
quence of alternate squares F -squares, and the other sequence E-squares. The
symbols on E-squares will be liable to erasure. The symbols on F -squares form
a continuous sequence. . . . There is no need to have more than one E-square
between each pair of F -squares: an apparent need of more E-squares can be
satisfied by having a sufficiently rich variety of symbols capable of being printed
on E-squares [1, p. 235].
Let’s examine the Englishman’s use of these two types of squares. De-
termine the output of the following Turing machine, which begins with the
tape
X . . .
and the scanner at the far left, reading the symbol X.
Configuration Behavior
m-config. symbol operation final m-config.
a X R a
a 1 R, R a
a blank P(1), R, R, P(1), R, R, P(0) b
b X E, R c
b other L b
c 0 R, P(X), R a
c 1 R, P(X), R d
d 0 R, R e
d other R, R d
e blank P(1) b
e other R, R e
5
Recall the meaning of the following symbols used for operations.
• R: Move one position to the right.
• L: Move one position to the left.
• E: Erase the currently scanned square
• P( ): Print whatever is in parentheses in the current square.
(Task 5) What is the precise output of the machine as it just finishes
configuration a and enters configuration b for the first time? Justify your
answer. [4 points]
(Task 6) What is the precise output of the machine as it just finishes
configuration a and enters configuration b for the second time? Justify your
answer. [4 points]
(Task 7) What is the precise output of the machine as it just finishes
configuration a and enters configuration b for the third time? Justify your
answer. [4 points]
(Task 8) Guess what the output of the machine is as it just finishes con-
figuration a and enters configuration b for the n-th time. Use induction to
prove that your guess is correct. Be sure to carefully write the details of this
proof by induction. [5 points]
Imagine a Turing machine, which when given two arbitrary natural numbers,
n and m, will compute the product n ·m. Suppose that the machine begins
with the tape
A 1 1 . . . 1 1 B 1 1 . . . 1 1 C
where the number of ones between A and B is n, the number of ones between
B and C is m, and the machine begins scanning the tape at the far left,
reading the symbol A. The output of the machine should be:
A 1 . . . 1 B 1 . . . 1 C 1 1 . . . 1 D
where the number of ones between C and D is n ·m.
If T denotes the Turing machine which multiplies n and m together, so
that the value of T (n, m) is n ·m, then for n ∈ N,
T (n, 1) = n
and for m ∈ N, m ≥ 2, we have
T (n, m) = T (n, m− 1) + n.
6
Such an equation provides an example of a recursively defined function, an
important topic in computer science. In this case, the algorithm for multi-
plication, T , is defined in terms of addition, a more elementary operation.
REFERENCES:
[1] Turing, A. M., “On Computable Numbers with An Application to the
Entscheidungsproblem,” Proceedings of the London Mathematical Society,
42, 1936, pp. 230–265.
7





























































































































































































































学霸联盟