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