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.