<< Предыдущая стр. 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 стр.)ОГЛАВЛЕНИЕ Следующая >>