Problem Solving in Automata, Languages, and Complexity

5.1 Universal Turing Machines 227

Example 5.1 Show thut the set L = {x E (0, l}* 1 x is a legal code} is
primitive recursive.

Proof. A string x is legal if and only if the following hold:

(i) It is of the form (5.1);

(ii) For each instruction code 10ilO~lO~lOelOhl of x, h is either 1 or 2;

(iii) No two instruction codes start with the same substring 10ilOjl;

(iv) If the maximum state is qn, then no instruction begins with 107.

We first check that the set of strings of the form (5.1) is a regular set

In Exercise 5 of Section 4.8, we showed that all context-free languages are

primitive recursive. Since a regular language is context-free, we see that con-

dition (i) is primitive recursive.

Recall that sub(u,v) = [ u is a substring of v], head@, V) = [U is a prefix of

V] and tail@, v) = [ u is a suffix of V] are all primitive recursive predicates (Ex-

ample 4.42).l Define the predicate instr(y, x) to mean that y is an instruction

code of x; or, equivalently,

y E 10+10+10+10+10+1 and sub(y, z).

Then, it is clear that instr is primitive recursive.

We now check the other three conditions. For condition (ii), we note that

it is equivalent to

(~Y)lYl<lSI - (Vh) l<h<lXl - - [[instr(y,x) and tuil(lOQ, y)] > [h = 1 or h = 211.

Similarly, condition (iii) is equivalent to

(VY)I?JI<lxI (v~)l~I<I~I[[i~str(Y, 4 and inste, 4 and

(3&+1~& - E lO+lO+l and heud(w,y) and heud(w, z)]] 3 y = z].

For condition (iv), we note that the maximum state number of x is

muxstute(x) = ( maxlc)l<k<l,l(3i)l<i<l~l - - -- (~~)l<j<l~l - -

(3e)l<e<I~l(3h)l~hII~I -- instr( 1Oi 1Oj 10’ 10elOh 1, x).

So, it is a primitive recursive function. (See Exercise 3 of Section 4.6 for the

operation max.) Now, condition (iv) can be stated as

W>i<l~l - (VY)lvl<lGI - [ instr(y,x) and heud(lOQ,y)^3 i < muxstute(x)]. q

‘When Cl = {O,l} is understood, we write sub(u, u) for subq (u, v), etc.