Problem Solving in Automata, Languages, and Complexity

222 TURING MACHINES

Theorem 4.47 Every partial recursive function is Turing-computable.

Proof. From the above lemma, we know that we only need to prove that all

partial recursive functions defined on integers are Turing-computable, with

respect to the representation Cl = {l}. In the following, whenever there is

no confusion, we do not distinguish integer n from its representation 1”.

First, it is easy to see that the zero function c and the successor function CT

are Turing-computable. Furthermore, Example 4.8 showed that the projection

functions Y$ are all Turing-computable. So, all initial functions are Turing-

computable.

Next, we need to prove that the operations of composition, primitive re-

cursion and minimization preserve Turing-computability.

Composition. Assume that g : N” + N and hi : N” + N, 1 < - i < - m,

are computed by 3-tape TM’s A&, 0 < i < m, respectively. We design a new

four-tape TM IM that computes function-

as follows:

(1) M repeats step 2 for i = 1,2,... , m.

(2) M simulates TM A&i on input (nl,... , nk), using tape 1 as the input

tape, tape 2 as the output tape and tape 3 as the work tape. More

precisely, for each simulation of machine A& it starts with the tape

configuration

(B~“‘B~~~B.. l BlnkB, BltlBog VBlt’-lB,BE&

and ends with the tape configuration

(B~B~EI.. l ~iT3, BP~B.. •BP~-~B~%, BE),

where tj = hj(nl,.. .,nk), for j = I,.. .,m,

(3) M simulates TM A& on input (tl, t2,. “9 t m ) 1 using tape 2 as the input

tape, tape 3 as the output tape and tape 4 as the work tape.

Note that when M finishes the simulation of Mm, the configuration of tape

2 is

BltlB l l l BIt2B l l .B+E#,

and so the set up of the input to Mo is correct.

Primitive Recursion. Assume that g : N” + N and h : Nk+2 + N are

computed by 3-tape TM’s &$ and A&, respectively, and assume f : Nk+l +

N is defined from g and h by primitive recursion. We can design a new

multi-tape TM 1M to compute f in a bottom-up fashion: it first computes

t0 = g(n1, l l l^9 nk), and then uses this to to compute tl = h(nl,... , nk, 0, to),

and repeatedly computes ti+l = h(nl,... , nk, i, ti) for i = 1,2,.. ., m (cf. the

remark after Theorem 4.37). The detail of the machine M is left as an exercise.