<<

. 2
( 10 .)



>>

ing machines, which were introduced more or less simultaneously by
Alan Turing and Emil Post in 1936.1 Like most real-life digital com-
puters, Turing machines have two main parts, a processing unit and
a memory (which doubles as the input/output device), which we will
consider separately before seeing how they interact. The memory can
be thought of as a tape, without end in one direction, which is divided
up into cells like the frames of a movie. The Turing machine proper is
the processing unit. It has a scanner or “head” which can read from or
write to a single cell of the tape, and which can be moved to the left
or right one cell at a time.
Tapes. The ¬rst thing we have to do in describing a Turing ma-
chine is to specify what symbols it is able to read and write on its
tape.
Definition 10.1. An alphabet is a non-empty ¬nite set Σ, the el-
ements of which are called symbols, such that 0 ∈ Σ.
/
The reason we don™t allow Σ to contain 0 is that we will use 0 to
mark all the otherwise blank cells on a tape.
Definition 10.2. Given an alphabet Σ, a tape (with entries from
Σ) is an in¬nite sequence
a = a0 a1 a2 a3 . . .
such that for each integer i the cell ai ∈ {0} ∪ Σ. The ith cell is said
to be blank if ai is 0, and marked if ai is a symbol from Σ.
A blank tape is one in which every cell is 0. It will be shown later on
that it is possible to restrict the alphabet to just one non-blank symbol
without essentially diminishing what a Turing machine can accomplish,
but it is usually convenient to have more symbols about when actually
devising a Turing machine for a particular task.
1
Both papers are reprinted in [4]. Post™s brief paper gives a particularly lucid
informal description.
7
8 10. TURING MACHINES

Example 10.1. A blank tape looks like:
000000000000000000000000 · · ·
The 0th cell is the leftmost one, cell 1 is the one immediately to the
right, cell 2 is the one immediately to the right of cell 1, and so on.
Letting our alphabet be Σ = { 1, x, y }, the following is a slightly
more exciting tape:
010xx1011x1y01yyx000000000000000 · · ·
In this case, cell 1 contains a 1, as do cells 5, 7, 8, 10, and 13; cells 3,
4, 9, and 16 each contain an x; cells 11, 14, and 15 each contain a y;
and all the rest contain a 0.
Problem 10.1. Write down tapes satisfying the following; you may
use any appropriate alphabets.
1. Entirely blank except for cells 3, 12, and 20.
2. Entirely marked except for cells 0, 2, and 3.
3. Entirely blank except for a block of ¬ve consecutive cells just to
the right of cell 0.
4. Entirely blank except that 1025 is written out in binary just to
the right of cell 2.
To keep track of which cell the Turing machine™s scanner is at, plus
some other information, we will usually attach additional information
to our description of the tape.
Definition 10.3. A tape position is a triple (i, s, a), where i and s
are natural numbers with s > 0, and a is a tape. Given a tape position
(i, s, a), we will refer to cell i as the scanned cell and to s as the state.
The number s mentioned above will be used to keep track of which
instruction the Turing machine is to execute next.

Conventions for tapes. Unless stated otherwise, we will assume
that all but ¬nitely many cells of any given tape are blank, and that any
cells not explicitly described or displayed are blank. We will usually
depict as little of a tape as possible and omit the · · · s we used above.
Thus
010xx1011x1y01yyx
represents the tape given in the Example 10.1. In many cases we will
also use z n to abbreviate n consecutive copies of z, so the same tape
could be represented by
010x2 1012 x1y01y 2 x .
10. TURING MACHINES 9

Similarly, if σ is a ¬nite sequence of elements of Σ ∪ {0}, we may write
σ n for the sequence consisting of n copies of σ stuck together end-to-
end. For example, (010)3 is 010010010.
In displaying tape positions we will usually underline the scanned
cell and write s to the right of the tape. For example, we would display
the tape position using the tape from Example 10.1 with cell 4 being
scanned and state 2 as follows:
010xx1012 x1y01y 2 x : 2
Problem 10.2. Using the tapes you gave in the corresponding part
of Problem 10.1, write down tape positions satisfying the following con-
ditions.
1. Cell 7 being scanned and state 4.
2. Cell 4 being scanned and state 1.
3. Cell 0 being scanned and state 3.
4. Cell 3 being scanned and state 413.
Turing machines. The “processing unit” of a Turing machine is
just a ¬nite list of speci¬cations describing what the machine will do
in various situations. (Remember, this is an abstract computer . . . )
The formal de¬nition may not seem to amount to this at ¬rst glance.
Definition 10.4. A Turing machine (with alphabet Σ) is a func-
tion M such that for some natural number n,
dom(M) ⊆ {1, . . . , n} — ({0} ∪ Σ)
and
ran(M) ⊆ ({0} ∪ Σ) — {’1, 1} — {1, . . . , n} .
Note that M need not be de¬ned for all possible pairs
(s, j) ∈ {1, . . . , n} — ({0} ∪ Σ) .
We will sometimes refer to a Turing machine simply as a machine
or TM . If n ≥ 1 is least such that M satis¬es the de¬nition above, we
shall say that M is an n-state Turing machine and that {1, . . . , n} is
the set of states of M.
Intuitively, we have a processing unit which has a ¬nite list of basic
instructions, the states, which it can execute. Given a combination of
current state and the symbol marked in the cell of the tape currently
being scanned that it is equipped to handle, the processor speci¬es
• a symbol to be written in the currently scanned cell, overwriting
the symbol being read, then
• a move of the scanner one cell to the left or right, and then
• the next instruction to be executed.
10 10. TURING MACHINES

That is, M(s, c) = (b, d, t) means that if our machine is in state s (i.e.
executing instruction number s), scanning the ith cell, and ai = c (i.e.
cell i contains c), then the machine M should
• set ai = b (i.e. write b instead of c in the scanned cell), then
• move the scanner to ai+d (i.e. move one cell left if d = ’1 and
one cell right if d = 1), and then
• enter state t (i.e. go to instruction t).
If our processor isn™t equipped to handle input c for instruction s (i.e.
M(s, a) is unde¬ned), then the computation in progress will simply
stop dead.
Example 10.2. We will usually present Turing machines in the
form of a table, with a row for each state and a column for each possible
entry in the scanned cell. Instead of ’1 and 1, we will usually use L
and R when writing such tables in order to make them more readable.
Thus the table
M 0 1
1 1R2 0R1
2 0L2
de¬nes a Turing machine M with alphabet {1} and two states such that
M(1, 0) = (1, 1, 2), M(1, 1) = (0, 1, 1), and M(2, 0) = (0, ’1, 2), but
M(2, 1) is unde¬ned. (So M has domain { (1, 0), (1, 1), (2, 0) } and
range { (1, 1, 2), (0, 1, 1), (0, ’1, 2) }.) If the machine M were faced
with the tape position
01001111 : 1 ,
it would, being in state 1 and scanning a cell containing 0,
• write a 1 in the scanned cell,
• move the scanner one cell to the right, and
• go to state 2.
This would give the new tape position
01011111 : 2 .
Since M doesn™t know what to do on input 1 in state 2, the computation
could go no further.
Problem 10.3. In each case, give the table of a Turing machine
M meeting the given requirement.
1. M has alphabet {x, y, z} and has three states.
2. M has alphabet {1} and changes 0 to 1 and vice versa in any
cell it scans.
3. M is as simple as possible. How many possibilities are there
here?
10. TURING MACHINES 11

Computations. Informally, a computation is a sequence of actions
of a machine M on a tape according to the rules above, starting with
instruction 1 and the scanner at cell 0 on the given tape. A computation
ends (or halts) when and if the machine encounters a tape position
which it does not know what to do in or runs o¬ the left end of the tape.
(If it never does either, the computation will never end ” not quite
like real computers, Turing machines succeed only when they crash!)
The formal de¬nition makes all this seem much more formidable.
Definition 10.5. Suppose M is a Turing machine. Then:
• If p = (i, s, a) is a tape position using the same alphabet as M
and M(s, ai ) = (b, d, t) is de¬ned, then M(p) = (i + d, t, a ) is
the successor tape position, where ai = b and aj = aj for j = i.
• A partial computation with respect to M is a sequence p1 p2 . . . pk
of tape positions such that p +1 = M(p ) for each < k.
• A partial computation p1 p2 . . . pk with respect to M is a compu-
tation (with respect to M) with input tape a if p1 = (0, 1, a) and
M(pk ) is unde¬ned. The output tape of the computation is the
tape of the ¬nal tape position pk .
Note that a computation must have only ¬nitely many steps.
Example 10.3. Let™s see the machine M of Example 10.2 perform
a computation. Our input tape will be a = 1100, that is, the tape
which is entirely blank except that a0 = a1 = 1. The initial tape
position of the computation of M with input tape a is then
1100 : 1 .
The subsequent steps in the computation are:
0100 : 1
0000 : 1
0010 : 2
0010 : 2
We leave it to the reader to check that this is indeed a partial com-
putation with respect to M. Since M(2, 1) is unde¬ned the process
terminates at this point and this partial computation is indeed a com-
putation.
Problem 10.4. Give the (partial) computation of the Turing ma-
chine M of Example 10.2 when the input tape is:
1. 00.
2. 110.
12 10. TURING MACHINES

3. The tape with all cells marked with 1s and cell 5 being scanned.
Problem 10.5. For which possible input tapes does the partial com-
putation of the Turing machine M of Example 10.2 eventually termi-
nate?
Problem 10.6. Find a Turing machine that (eventually!) ¬lls a
blank input tape with the pattern xyyz3xyyz3xyyz3 . . . .
Problem 10.7. Find a Turing machine with alphabet {$, @}that
never halts, no matter what is on the tape.
Example 10.4. The Turing machine P given below is intended to
produce output 01m on input 01n 01m whenever n, m > 0.
P 0 1
1 0R2
2 1R3
3 0R4 0R3
4 0R4 0R5
5 0L8 1L6
6 0L6 1R7
7 1R4
8 0L8 1L9
9 1L9
Trace P ™s computation on, say, input 013 014 to see how it works.
Problem 10.8. In each case, ¬nd a Turing machine (with the al-
phabet of your choice) that:
1. Halts with output 014 on input 0.
2. Halts with output 01n 0 on input 00n 1.
3. Halts with output 012n on input 01n .
4. Halts with output 0(10)n on input 01n .
5. Halts with output 01m 01n on input 01m 0k 1n , if n, m, k > 0.
6. Halts with output 01m 01n 01k on input 01n 01k 01m , if n, m, k > 0.
7. Halts with output 01m 01n 01k 01m 01n 01k on input 01m 01n 01k , if
n, m, k > 0.
8. On input 01m 01n , where m, n > 0, halts with output 01 if m = n
and output 011 if m = n.
It is quite possible to ¬nd such machines with just {1} as an alphabet.
Note. It doesn™t matter what the machine you de¬ne in each case
does on other inputs, so long as it does the right thing on the given
one(s).
CHAPTER 11


Variations and Simulations

The de¬nition of a Turing machine given in Chapter 10 is arbitrary
in a number of ways, among them the use of an arbitrary ¬nite al-
phabet, a single read-write scanner, and a single one-way in¬nite tape.
One could restrict the de¬nition we gave by allowing
• the machine to move the scanner only to one of left or right in
each state,
• only {1} as an alphabet,
or both, among various possibilities. One could also de¬ne apparently
more powerful Turing machines by allowing the use of
• two-way in¬nite tapes,
• multiple tapes,
• two- and higher-dimensional tapes,
or various combinations of these, among many other possibilities. We
will construct a number of Turing machines that simulate others with
additional features; this will show that none of the modi¬cations men-
tioned above really change what the machines can compute.

Example 11.1. Consider the following Turing machine:
M 0 1
1 1R2 0L1
2 0L2 1L1
Note that in state 1, this machine may move the scanner to either
the left or the right, depending on the contents of the cell being scanned.
We will construct a Turing machine, with alphabet {1}, that emulates
the action of M on any input, but which moves the scanner to only
one of left or right in each state. There is no problem with state 2 of
M, by the way, because in state 2 M always moves the scanner to the
left.
The basic idea is to add some states to M which replace part of the
description of state 1.
13
14 11. VARIATIONS AND SIMULATIONS

M 0 1
1 1R2 0R3

<<

. 2
( 10 .)



>>