230 COMPUTABILITY THEORY
tape 2 to the next 1 to the right (if h = 2) or to the left (if h = 1). When
it moves right, it also checks if this is the rightmost 1; if so, it adds 031 to
its right. When it moves left, it checks whether it is currently scanning the
leftmost 1; if so, it adds lo3 to its left and moves the tape head to scan the
leftmost 1.
If such an instruction is not found, then U determines whether the current
state stored in tape 3 is the final state qn or not (i.e., whether it is equal to
ma&ate(y)). If it is the final state, then it halts and accepts. Otherwise, it
enters an infinite loop and never halts. (In practice, it halts and rejects.)
We leave the details of the simulation as an exercise (see Exercise 2 of this
section).
We have just proved the following theorem:
Theorem 5.3 For every k > 1, the partial f2snction a’ : ((0, l})“+l +
{O,l}, defined by -
is partial recursive.The coding of a DTM by a string and the existence of a universal DTM play
an important role in computability theory. So, let us study the computation
of the universal DTM in more detail. First, let us encode each configuration
of A& by a single string in (0, 1)‘. That is, the configuration
of the machine M9 is encoded by
We say a string u is a legal code of a configuration if u is of the above form.
Example 5.4 Show that the following predicates are primitive recursive:
(a) k7aqu, Y) = [ u is a legal code of a configuration of MY].
(b) fina+, Y) = [kP@~ Y) and u is a final configuration].
(c) next(u, v, Y) = [if final(u, y) then u = v else u FM, v].Proof. For any string u of length greater than 5, let u’ = substr(u, 3,luj - 4)..
(a) We observe that u is a legal code of a configuration of J& if and only ilf
(i) u E 11(10+)*110+11(0+1)*11,
(ii) (Vi)l~~~lUI[Su~(llO”11, -- u’) 3 i < - maxstate(y and(iii) (Yi)l<j+~[ - - sub(lOjl,u’) and neg(sub(llOjll,u’))^3 j 5 maxsym(y)],