Problem Solving in Automata, Languages, and Complexity

5.1 Universal Turing Machines 231

where maxstate is the maximum state number of My and maxsym( y) is
the maximum symbol number of MY.
The function maxstute has been shown to be primitive recursive in Example
5.1. The function muxsym can be proved to be primitive recursive in a similar
way. From these results, we see that legal is primitive recursive too.
(b) finuZ(u, y) is true if and only if legal@, y) and llOma~state(~)ll is a
substring of u’.
(c) We note that the first condition is easily checked by (b) above. It is
not hard to see that the condition [u FM, v] is also primitive recursive (see
Exercise 2). Therefore, the predicate next is also primitive recursive. cl

Example 5.5 Show thut the following functions are primitive recursive:

(u) inat - k (xl,...,xk,y) = the initiul configurution of MY on inputs (x1,.. .,

xk), encoded us described above.

(V output(u, y) =

= 0 otherwise.

the output in u if u is a finul configuration of MY, und

Proof. (a) First, we recall that each input symbol 0 is encoded by 0, symbol

1 by 00, and symbol blank B is by 03. Thus, it is clear that the function

Y( X > = x’ is primitive recursive, and so

initk(Xl,... , Xk, y) = lX~1031X~l l l l 1031X~1101103111

is primitive recursive.

(b) Recall that the output of u is the longest tail in (0, l}* of the substring

to the left of the state symbol of u. So, let

left(u) = (minv)l,(<lul(32U)lull<lul(3lc)k<lul[llvll0”llwlll - = u],

and we have

output(u, Y) = if finuZ(u, y) then (maxz)l,l+l[tuiZ(g(z), - left(u))] eZse 0.^0

The following two predicates will be used in the next few sections.

Lemma 5.6 The following predicates are primitive recursive:

(a) For each k > 1, huZt”(xl,... , xk, y, t) = [MY halts on inputs (x1,... , xk)

in at most t moves].

(b) For each k > 1, printk(xl,.. .,xk, x, y, t) = [MY huZts on inputs

(Xl, ’ l l 7 xk) in at most t moves and outputs z].

Proof. (a) D e ne fi f unction f (u, v, y, t) to mean that there exists ug, ~1,... , ut

such that u = UO, v = ut and next(ui, ui+l, y) for all i = O,l,.. .,t - 1. Then,

f is primitive recursive:

f(u, v, Y, 0) = [u = VI,

f (u, v, YG + 1) = (32U)l,l<l,(+(y([next(u, w, Y) and f (?-4 v, Y,t)l*