phabet {1}, (i, s, a) is a tape position for M. Find a Turing machine

R which on input

0 M 03m+33 (i, s, a)

halts with output

0 M 03m+31 11+c 01’c (i, s, a) ,

where c = ai .

Problem 12.10. Suppose M is an m-state Turing machine with

alphabet {1}, (i, s, a) is a tape position for M, and j ∈ {0, 1}. Find a

Turing machine W which on input

0 M 03m+31 11+j 01’j (i, s, a)

halts with output

0 M 03m+31 11+j 01’j (i, s, a ) ,

where a is identical to a except that ai = j.

Problem 12.11. Suppose M is an m-state Turing machine with

alphabet {1}, (i, s, a) is a tape position for M, and c ∈ {0, 1}. Find a

Turing machine E which on input

0 M 03m+31 11+c 01’c (i, s, a)

halts with output

M(s, c) 0m+18 11+c 01’c (i, s, a) .

0M

Problem 12.12. Suppose M is an m-state Turing machine with

alphabet {1} and (i, s, a) is a tape position for M. Find a Turing

machine S which on input

0 M 03m+33 (i, s, a)

halts with output

0 M 03m+33 M(i, s, a) .

Using these machines, we can ¬nally assemble an universal Turing

machine.

22 12. UNIVERSAL MACHINES & THE HALTING PROBLEM

Theorem 12.13. There is a Turing machine U such that, for any

m ≥ 1, m-state Turing machine M with alphabet {1}, and tape position

(i, s, a) for M, U acts on the input position

0 M 03m+33 (i, s, a)

as follows:

• If M, starting from position (i, s, a), eventually halts in position

(j, t, b), then U eventually halts in the position

0 M 03m+33 (j, t, b) .

• If M, starting from the initial tape position (i, s, a), eventually

runs o¬ the left end of its tape, U eventually runs o¬ the left end

of its own tape.

• If M, starting from the initial tape position (i, s, a), never halts,

then U never halts.

The Halting Problem. Given that we are using Turing machines

to formalize the notion of an e¬ective method, one of the di¬culties

with solving the Halting Problem is representing a given Turing ma-

chine and its input tape as input for another machine. As this is exactly

what was done above, we can now formulate a precise version of the

Halting Problem and solve it.

The Halting Problem. Is there a Turing machine T which, for

any m ≥ 1, m-state Turing machine M with alphabet {1}, and tape a

for M, halts on input

0 M 03m+33 (0, 1, a)

with output 011 if M halts on input a, and with output 01 if M does

not halt on input a?

Note that this version of the Halting Problem is equivalent to our

original one only if Church™s Thesis is true.

Problem 12.14. Find a Turing machine C which, for any Turing

machine M with alphabet {1}, on input

0M

eventually halts with output

0 (0, 1, M ) .

Theorem 12.15. There is no Turing machine T which, for any

m ≥ 1, m-state Turing machine M with alphabet {1}, and tape a for

M, halts on input

0 M 03m+33 (0, 1, a)

12. UNIVERSAL MACHINES & THE HALTING PROBLEM 23

with output 011 if M halts on input a, and with output 01 if M does

not halt on input a.

24 12. UNIVERSAL MACHINES & THE HALTING PROBLEM

CHAPTER 13

Computable and Non-Computable Functions

So far, the only substantial facts we have about what Turing ma-

chines can do is that they can be used to simulate other Turing ma-

chines, but cannot solve the Halting Problem. Neither fact is trivial,

but neither is really interesting unless Turing machines can also be

used to handle more natural computational problems. Arithmetic is a

common source of such problems in the real world; indeed, any notion

of computation that can™t handle it is unlikely to be of great use.

Notation and conventions. To keep things as simple as pos-

sible, we will stick to computations involving the natural numbers,

i.e. the non-negative integers, the set of which is usually denoted by

N = { 0, 1, 2, . . . }.. The set of all k-tuples (n1 , . . . , nk ) of natural num-

bers is denoted by Nk . For all practical purposes, we may take N1 to

be N by identifying the 1-tuple (n) with the natural number n.

For k ≥ 1, f is a k-place function (from the natural numbers to the

natural numbers), often written as f : Nk ’ N, if it associates a value,

f(n1 , . . . , nk ), to each k-tuple (n1, n2 , . . . , nk ) ∈ Nk . Strictly speaking,

though we will frequently forget to be explicit about it, we will often

be working with k-place partial functions which might not be de¬ned

for all the k-tuples in Nk . If f is a k-place partial function, the domain

of f is the set

dom(f) = { (n1 , . . . , nk ) ∈ Nk | f(n1 , . . . , nk ) is de¬ned } .

Similarly, the image of f is the set

im(f) = { f(n1 , . . . , nk ) | (n1 , . . . , nk ) ∈ dom(f) } .

In subsequent chapters we will also work with relations on the nat-

ural numbers. Recall that a k-place relation on N is formally a subset

P of Nk ; P (n1 , . . . , nk ) is true if (n1 , . . . , nk ) ∈ P and false otherwise.

In particular, a 1-place relation is really just a subset of N.

Relations and functions are closely related. All one needs to know

about a k-place function f can be obtained from the (k + 1)-place

relation Pf given by

Pf (n1 , . . . , nk , nk+1 ) ⇐’ f(n1 , . . . , nk ) = nk+1 .

25

26 13. COMPUTABLE AND NON-COMPUTABLE FUNCTIONS

Similarly, all one needs to know about the k-place relation P can be

obtained from its characteristic function :

1 if P (n1 , . . . , nk ) is true;

χP (n1 , . . . , nk ) =

0 if P (n1 , . . . , nk ) is false.

The basic convention for representing natural numbers on the tape

of a Turing machine is a slight variation of unary notation : n is rep-

resented by 1n+1 . (Why would using 1n be a bad idea?) A k-tuple

(n1 , n2, . . . , nk ) ∈ N will be represented by 1n1 +1 01n2 +1 0 . . . 01nk +1 , i.e.

with the representations of the individual numbers separated by 0s.

This scheme is ine¬cient in its use of space ” compared to binary

notation, for example ” but it is simple and can be implemented on

Turing machines restricted to the alphabet {1}.

Computable functions. With suitable conventions for represent-

ing the input and output of a function on the natural numbers on the

tape of a Turing machine in hand, we can de¬ne what it means for a

function to be computable by a Turing machine.

Definition 13.1. A k-place function f is Turing computable, or

just computable, if there is a Turing machine M such that for any

k-tuple (n1 , . . . , nk ) ∈ dom(f) the computation of M with input tape

01n1 +1 01n2 +1 . . . 01nk +1 eventually halts with output tape 01f (n1 ,...,nk )+1 .

Such an M is said to compute f.

Note that for a Turing machine M to compute a function f, M

need only do the right thing on the right kind of input: what M does

in other situations does not matter. In particular, it does not matter

what M might do with k-tuple which is not in the domain of f.

Example 13.1. The identity function iN : N ’ N, i.e. iN(n) = n,

is computable. It is computed by M = …, the Turing machine with an

empty table that does absolutely nothing on any input.

Example 13.2. The projection function π1 : N2 ’ N given by

2

2

π1 (n, m) = n is computed by the Turing machine:

2

P1 0 1

1 0R2

2 0R3 1R2

3 0L4 0R3

4 0L4 1L5

5 1L5

13. COMPUTABLE AND NON-COMPUTABLE FUNCTIONS 27

2

P1 acts as follows: it moves to the right past the ¬rst block of 1s

without disturbing it, erases the second block of 1s, and then returns

to the left of ¬rst block and halts.

The projection function π2 : N2 ’ N given by π1 (n, m) = m is also

2 2

computable: the Turing machine P of Example 10.4 does the job.

Problem 13.1. Find Turing machines that compute the following

functions and explain how they work.

1. O(n) = 0.

2. S(n) = n + 1.

3. Sum(n, m) = n + m.

n’1 n≥ 1

4. Pred(n) = .

0 n=0

n’m n≥m

5. Diff(n, m) = .

0 n<m

3

6. π2 (p, q, r) = q.

We will see how to build complex functions computable by Turing

machines out of simpler ones in the next chapter.

A non-computable function. In the meantime, it is worth ask-

ing whether or not every function on the natural numbers is com-

putable. No such luck!

Problem 13.2. Show that there is some 1-place function f which

is not computable by comparing the number of such functions to the

number of Turing machines.

The argument hinted at above is unsatisfying in that it tells us there

is a non-computable function without actually producing an explicit

example. We can have some fun on the way to one.

Definition 13.2 (Busy Beaver Competition). A machine M is an

n-state entry in the busy beaver competition if:

• M has a two-way in¬nite tape and alphabet {1};

• M has n + 1 states, but state n + 1 is used only for halting (so

both M(n + 1, 0) and M(n + 1, 1) are unde¬ned);

• M eventually halts when given a blank input tape.

M™s score in the competition is the number of 1™s on the output tape of

its computation from a blank input tape. The greatest possible score

of an n-state entry in the competition is denoted by Σ(n).

Note that there are only ¬nitely many possible n-state entries in the

busy beaver competition because there are only ¬nitely many (n + 1)-

state Turing machines with alphabet {1}. Since there is at least one

28 13. COMPUTABLE AND NON-COMPUTABLE FUNCTIONS

n-state entry in the busy beaver competition for every n ≥ 0 , it follows

that Σ(n) is well-de¬ned for each n ∈ N.

Example 13.3. M = … is the only 0-state entry in the busy beaver

competition, so Σ(0) = 0.

Example 13.4. The machine P given by

P 0 1

1 1R2 1L2

2 1L1 1L3

is a 2-state entry in the busy beaver competition with a score of 4, so

Σ(2) ≥ 4.

The function Σ grows extremely quickly. It is known that Σ(0) = 0,

Σ(1) = 1, Σ(2) = 4, Σ(3) = 6, and Σ(4) = 13. The value of Σ(5) is

still unknown, but must be quite large.1

Problem 13.3. Show that:

1. The 2-state entry given in Example 13.4 actually scores 4.

2. Σ(1) = 1.

3. Σ(3) ≥ 6.

4. Σ(n) < Σ(n + 1) for every n ∈ N.

Problem 13.4. Devise as high-scoring 4- and 5-state entries in the

busy beaver competition as you can.

The serious point of the busy beaver competition is that Σ is not a

Turing computable function.

Proposition 13.5. Σ is not computable by any Turing machine.

Anyone interested in learning more about the busy beaver com-

petition should start by reading the paper [10] in which it was ¬rst

introduced.

1

The best score known to the author as of this writing by a 5-state entry in

the busy beaver competition is 4098. One of the two machines achieving this score

does so in a computation that takes over 40 million steps! The other requires only

11 million or so . . .

CHAPTER 14

Primitive Recursive Functions

Starting with a small set of computable functions, and applying

computable ways of building functions from simpler ones, we will build

up a useful collection of computable functions. This will also go a long

way toward giving us a characterization of computable functions which

does not mention any particular computing devices.

The initial functions. The set of computable functions that will

be the fundamental building blocks for all that follows is in¬nite only

because of the presence of all the projection functions.

Definition 14.1. The following are the initial functions:

• O, the 1-place function such that O(n) = 0 for all n ∈ N;

• S, the 1-place function such that S(n) = n+ 1 for all n ∈ N; and,

• for each k ≥ 1 and 1 ¤ i ¤ k, πi , the k-place function such that

k

πi (n1 , . . . , nk ) = ni for all (n1 , . . . , nk ) ∈ Nk .

k

O is often referred to as the zero function, S is the successor function,

k

and the functions πi are called the projection functions.

Note that π1 is just the identity function on N. We have already ob-

1

1 2 2 3

served that O, S, π1 , π1 , π2 , and π2 are Turing computable in Chapter

13.

Problem 14.1. Show that all of the initial functions are Turing

computable.