<<

. 4
( 10 .)



>>

Problem 12.9. Suppose M is an m-state Turing machine with al-
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.

<<

. 4
( 10 .)



>>