<<

. 3
( 10 .)



>>

2 0L2 1L1
3 0L4 1L4
4 0L1
This machine is just like M except that in state 1 with input 1,
instead of moving the scanner to the left and going to state 1, the
machine moves the scanner to the right and goes to the new state 3.
States 3 and 4 do nothing between them except move the scanner two
cells to the left without changing the tape, thus putting it where M
would have put it, and then entering state 1, as M would have.
Problem 11.1. Compare the computations of the machines M and
M of Example 11.1 on the input tapes
1. 0
2. 011
and explain why is it not necessary to de¬ne M for state 4 on input 1.
Problem 11.2. Given a Turing machine M with an arbitrary al-
phabet Σ, explain in detail how to construct a machine M that simu-
lates what M does on any input, but which moves the scanner only to
one of left or right in each state.
Problem 11.3. Given a Turing machine M with an arbitrary al-
phabet Σ, explain in detail how to construct a machine N with alphabet
{1} that simulates M.
To de¬ne Turing machines with two-way in¬nite tapes we need
only change the de¬nition of the tape: instead of having tapes be se-
quences a = a0, a1, a2, . . . indexed by N, we let them be sequences
b = . . . , b’2, b’1 , b0, b1 , b2, . . . indexed by Z. In de¬ning computa-
tions for machines with two-way in¬nite tapes, we adopt the same
conventions that we did for machines with one-way in¬nite tapes, such
as the scanner starts o¬ scanning cell 0 on the input tape. The only
real di¬erence is that a machine with a two-way in¬nite tape cannot
halt by running o¬ the left end of the tape . . .
Example 11.2. Consider the following two-way in¬nite tape Tur-
ing machine with alphabet {1}:
T 0 1
1 1L1 0R2
2 0R2 1L1
The biggest problem in trying to emulate T with a one-way in¬nite
tape Turing machine O is representing a two-way in¬nite tape on a
11. VARIATIONS AND SIMULATIONS 15

one-way in¬nite tape. To do this, we choose an alphabet for O with
malice aforethought:
{ S, S, 0, 0, 1, }
0 1 1
0 1 0 1

We can now represent the tape a,
. . . , a’2 , a’1 , a0, a1 , a2, . . . ,
for T by the tape a ,
, , , ... ,
a0 a1 a2
a’1 a’2
S


for O. In e¬ect, this device allows us to split O™s tape into two tracks,
each of which accomodates half of the tape of T .
The key remaining idea is to split each state of T into a pair of states
for O: one for the lower track and one for the upper track. One must
take care to keep various details straight: when O changes a “cell” on
one track, it should not change the corresponding “cell” on the other
track; directions are reversed on the lower track; one has to “turn a
corner” moving past cell 0; and so on.
O0 0 0 0 1 1 1
S 0 1 S 0 1
1 0 L1 S R3 0 L1 1 L1 S R2 0 R2 1 R2
1 1 1 1 0 0 0

2 0 R2 0 R2 0 R2 0 R2 S R3 1 L1 1 L1
1
0 S 0 1 0 1
3 1 R3 S R3 1 R3 0 L4 S R2 1 R3 1 L4
0 1 0 0 0 1
0
4 0 L4 S R2 0 L4 1 R3 S R3 0 L4 1 R3
0 0 0 0 1 1 1


States 1 and 3 are the upper- and lower-track versions, respectively,
of T ™s state 1; states 2 and 4 are the upper- and lower-track versions,
respectively, of T ™s state 2. We leave it to the reader to check that O
actually does simulate T . . .
Problem 11.4. Trace the (partial) computations of T , and their
counterparts for O, for each of the following input tapes for T , shown
with a bar over cell 0:
1. 0 (i.e. a blank tape)
2. 10
3. . . . 1111111 . . . (i.e. every cell marked with 1)
Problem 11.5. Explain in detail how, given a Turing machine N
with an arbitrary alphabet and a two-way in¬nite tape, one can con-
struct a Turing machine P with an one-way in¬nite tape that simulates
N.
Problem 11.6. Give a precise de¬nition for Turing machines with
two tapes. Explain how, given any such machine, one could construct
a single-tape machine to simulate it.
16 11. VARIATIONS AND SIMULATIONS

Problem 11.7. Give a precise de¬nition for Turing machines with
two-dimensional tapes. Explain how, given any such machine, one
could construct a single-tape machine to simulate it.
Taken together, these results mean that for the purposes of investi-
gating what can be computed in principle, we can use any of the above
variants on our de¬nition of Turing machines without loss of generality.
CHAPTER 12


Universal Turing Machines and the Halting
Problem

In Chapter 11 we devised techniques for constructing, given a par-
ticular Turing machine (of some type), a Turing machine (of another
type) that would simulate it. We will go further and construct an uni-
versal Turing machine (sometimes referred to as an UTM ): a machine
U that, when given as input (a suitable description of) some Turing
machine M and an input tape a for M, simulates the computation of
M on input a. In e¬ect, an universal Turing machine is a piece of
“hardware” that lets us treat Turing machines as “software”.
As a bonus, constructing such a machine will give us the tools we
will need to answer the following question:
The Halting Problem. Given a Turing machine M and an in-
put tape a, is there an e¬ective method to determine whether or not
M eventually halts on input a?
An e¬ective method to determine whether or not a given machine
will eventually halt on a given input ” short of waiting forever! ”
would be nice to have. For example, assuming Church™s Thesis is true,
such a method could let us identify computer programs which have
in¬nite loops before they tie computers up in knots.
An Universal Turing Machine. The ¬rst problem in trying to
build an universal Turing machine is ¬nding a suitable way to describe
the machine which is to be simulated, as well as its input tape, on the
input tape of the universal Turing machine. We can simplify our task
somewhat by restricting our attention to simulating Turing machines
with one-way in¬nite tapes whose alphabet is just {1}. We lose no
real generality in doing so since, by the results in Chapter 11, such
machines can do just as much as any other type. Among the many
possible ways of describing such machines as input, the one given below
is fairly straightforward but woefully ine¬cient.1 Essentially, it consists
1
For an example of a di¬erent method, one could combine the methods devel-
oped in Chapter 15 of representing Turing machines and tapes by integers with the
represention of integers on a tape used in Chapter 13.
17
18 12. UNIVERSAL MACHINES & THE HALTING PROBLEM

of simply listing the table de¬ning the Turing machine we wish to
specify.
Definition 12.1. Suppose M is a Turing machine with alphabet
{1} and m states. If 1 ¤ k ¤ m and i ∈ {0, 1} and M(k, i) = (j, d, ),
let
xM (k,i)y=11+k 0m’k 011+i 01’i 011+j 01’j 012+d 01’d 011+ 0m’ ;
if M(k, i) is not de¬ned, just let j = d = = 0 above.
That is, M(k, i) is a string of 2m + 13 0s and 1s which represents
the (k, i)th entry of M™s table in ¬ve distinct blocks, separated by single
0s:
1. one of length m + 1 codes k, represented by k + 1 1s followed by
a padding of 0s;
2. one of length 2 codes i, represented by 11 if i = 1 and 10 if i = 0;
3. one of length 2 codes j, represented by 11 if j = 1 and 10 if
j = 0;
4. one of length 3 codes d, represented by 111 if d = 1, 100 if
d = ’1, and 110 if d = 0 (i.e. if M(k, i) is unde¬ned);
5. one of length m + 1 codes , represented by + 1 1s followed by
a padding of 0s.
Definition 12.2. Suppose M is a Turing machine with alphabet
{1} and m states. The representation of M is
xM y=031m+1 03 xM (1,0)y02xM (1,1)y02xM (2,0)y02...02 xM (m,0)y02xM (m,1)y03 .

The representation of the machine M, M , then consists of an
initial string of three 0s, followed by m+1 1s giving the number of states
of M, three more 0s, the representations of the entries of the table of
M ” including the empty ones! ” listed in order and separated by
pairs of 0s, and a ¬nal string of three 0s.
Example 12.1. The representation of the Turing machine
E 0 1
1 0R2 ,
2 1L1 0R1
is
03 13 03 12 0010010013013 02 12 001201001200102 02 13 0100120102012 0 02 13 012 010013012 0 03 .

Problem 12.1. Pick a Turing machine di¬erent from the one in
Example 12.1 and give its representation.
Problem 12.2. Give a table for the Turing machine whose repre-
sentation is
0001100011010011011101100110110100111011000 .
12. UNIVERSAL MACHINES & THE HALTING PROBLEM 19

Problem 12.3. How many possible representations are there for a
given Turing machine?
Problem 12.4. Devise a more e¬cient way of representing Turing
machines than that given in De¬nition 12.2.
We now have at least one way of completely describing a given
Turing machine M to another Turing machine. Of course, we have not
yet considered how this description would actually be used, but we ¬rst
need to ¬nd a way to describe M™s input anyway. The most naive way
to do this is to simply have the input for M follow the description of M.
Unfortunately, this won™t do because we will need to keep track which
cell is being scanned and what the current state is while simulating
M. To solve this problem, we™ll go whole hog and describe not just the
tape a that M is reading but a complete tape position (i, s, a). (Recall
that i is an integer specifying the currently scanned cell, s is an integer
specifying which state M is in, and a is the tape.)
Definition 12.3. Suppose (i, s, a) is the tape position of an m-
state Turing machine with alphabet{1}. For each ∈ N, let
0 = i (i.e. cell is not being scanned)
c=
1 = i (i.e. cell is the scanned cell).
Let n be the least positive integer such that ak = 0 for all k > n, if
such exists. If so, the representation of (i, s, a) is the ¬nite sequence
(i, s, a) = 03 1s+1 0m’s 03 1c0 a0 1c1 a11c2 a2 . . . 1cn an 03 ;
otherwise, the representation of (i, s, a) is the in¬nite sequence
(i, s, a) = 03 1s+1 0m’s 03 1c0 a0 1c1 a11c2 a2 . . . .
That is, each cell of a is described by a triple of cells in the represen-
tation of a. The ¬rst cell of this triple is simply a marker, one indicates
whether or not the cell of a being described is the one being scanned
by M, and the last gives the content of the cell being described. The
representation of a tape position (i, s, a) then consists of three 0s, a
block of length m + 1 consisting of s + 1 1s padded out by m ’ s 0s,
another three 0s, the triples coding the cells of a, and, possibly, a ¬nal
three 0s to mark the end of the code. Since we assume tapes to have
all but ¬nitely many cells blank unless stated otherwise, almost all of
the representations of tape positions we will encounter will be ¬nite.
Example 12.2. Consider the tape position (2, 3, a) for a 5-state
Turing machine, where a = 01101. The representation of this tape
position is
000 111100 000 100 101 111 100 101 000 .
20 12. UNIVERSAL MACHINES & THE HALTING PROBLEM

Note that the only use of the 1 at the beginning of the represen-
tation of each cell is to mark the fact that a cell is being represented:
moving a scanner along the representation of a, one can identify the be-
ginning and end (if any) of the representation because one encounters
a 0 instead of a 1 marking the representation of another cell.
Problem 12.5. What are the representations of the following tape
positions for a 5-state Turing machine?
1. (0, 4, 11111)
2. (3, 1, 101011)
Problem 12.6. What tape positions are represented by the follow-
ing?
1. 0001100000110100100101101100100101100000
2. 00011111000101111101101101101101 . . .
Problem 12.7. Devise a more e¬cient way of representing tape
positions than that given in De¬nition 12.3.
We can now de¬ne our representation for M together with a tape
position (i, s, a). Except for inserting some extra 0s, this just amounts
to M followed by (i, s, a) .
Definition 12.4. Suppose M is an m-state Turing machine with
alphabet {1} and (i, s, a) is a tape position for M (so 1 ¤ s ¤ m). Then
the representation of the machine M together with the tape position
(i, s, a) is the sequence
M 03m+33 (i, s, a) .
The 3m+33 0s interpolated in the middle are intended to be used for
“scratch space” in the simulation of M by the universal Turing machine
we will construct in the following series of problems. Depending on
how these are solved, it may be possible to reduce ” or necessary to
increase! ” that 3m + 33.
Note. The statements of Problems 12.8“12.13 below assume the
use of the representation schemes given in De¬nitions 12.2“12.4. If you
would rather use the methods you devised in Problems 12.4 and 12.7,
by all means adapt the statements of Problems 12.8“12.13 accordingly.
You may ¬nd it convenient to give the machines you build in these
problems alphabets other than {1}, but one need not do so. (Why
doesn™t it really matter if one does?)
Problem 12.8. Suppose M is an m-state Turing machine with al-
phabet {1}, (i, s, a) is a tape position for M, and d = ±1. Find a
12. UNIVERSAL MACHINES & THE HALTING PROBLEM 21

Turing machine H which on input
0 M 03m+30 12+d 01’d (i, s, a)
halts with output
0 M 03m+30 12+d 01’d (i + d, s, a) .
H should extend the representation of a if necessary.

<<

. 3
( 10 .)



>>