Problem Solving in Automata, Languages, and Complexity

220 TURING MACHINES

Theorem 4.44 Every Turing-computable function is partial recursive.

Proof. From Theorem 4.19, we know that if a function f : (C)” --+ C
is computable by TM &!j then there is a grammar GM that simulates the
machine AI such that

f-(x1, x2,... , xk) = y ( (!k)derivec,([BxlBx2B... BxksB], [ByhB], t).

We could then, as demonstrated in Example 4.39, use this relation between f
and deriveGM to show that f is partial recursive.
We note, however, that f and deriveGM are two functions defined on
two different alphabets: f on C and deriveGM on A = I’ U Q U { [, I},
where C C - A (see Theorem 4.19). Assume that C = {sl, ~2,... , sm} and
A - - {sl,,s7n,s7n+l, l 9 sn}, with the ordering s1 4 l l l 4 sm < s,+l
-( l ’ -( sn. Then, a string x E C* represents the integer ~6~ (x) when we
deal with function f and it represents the in teger
grammar GM. Therefore, to use the above relati

LJp ( x >

.on, we

when we deal with

must first “change

base” to convert them into the same base A.

We define an integer function base~,~(i) = ~&c(i)). For instance, if

m = 5 and n = 10, then the string ~2~1~3 in C* represents 2*m2+1-m+3 = 58,

and ~2~1~3 in A* represents 2 l n2 + 1 l n + 3 = 213. The function basec > A then

maps 58 to 213.

Using Theorem 4.40, it is not hard to see that busec > A is primitive recursive:

b(JSQ,A(i) Z= (minj)j++ngE(‘,+~ - [lenSA = leng&)

and (~e)l<,<l~~,^(j)[subseq*(j,e, -- 1) = subseqc(i,&, l)]]-

Now we can complete the proof that f is partial recursive. Formally, we

need to show that the function f” : N” -+ N, defined by f”(nl,... , nk) =

~~l(f(Lc(nl), l l ‘7 LC(nk))), is primitive recursive. To do this, we first change

base to set up the initial and final strings of GM. That is, we define

gl(nl,... , nk) = concatik+4([, B, basec ) &zl), B,... , B, basec 9 R(nk), s, B,]),

and

ga(ml) = conc&([, B, bawz,A(ml), h, B,]).

Then, we get

f(nl, l l l 7 nk> = ml - (~t)d~veG,(gl(nl,...,nk),g2(ml),t),

where d&&eG, is the integer function associated with the string function

deriveGM over the alphabet A. By combining ml and t into a single integer

m2 = (ml, t), we can express f as

f”(nl,-,nk) = l((minm2)d~vec,(gl(nl,. .~,~~),g2(~(~2>)~~(~2>).

This shows that f” is partial recursive. cl