Problem Solving in Automata, Languages, and Complexity

232 COMPUTABILITYTHEORY

Now, we note that

h~~tk(~l,~-,~k,!/,t) = (321)1,1<luol+tlvl[f(Uo,v,y,t) - andfin+bY)],

where ~0 = inzt - k (x1,... , xfk, y). Thus, hult k l is primitive recursive.

(b) We note that printk(xl,... , xk, x, y,t) is the same as hcslt k (x1,.. l > xk,

y, t) above plus the extra condition that output(v, y) = z. cl

When k = 1, we write halt for hult’ and print for print’.

Exercises 5.1

1. Show that the following functions are primitive recursive:
   (a) state@, e, x) = [x is a legal code of a DTM AKJ and [substrjo ) 1)(x, i,
   ! + 2) is equal to 10’1 and represents a state qe in M].
   (b) chstute(x, i, j) = the code of a DTM which is obtained from A&
   by changing each state qi to qj, if x is a legal code of a DTM A&;
   and it is = 0, otherwise.
   (c) oo-Zoop(i, x) = [x is a legal DTM code] and [A& is undefined at
   state pi on any symbol in I’].


2. Complete the proof of Example 5.4(c).


3. Show the detail of how the universal DTM U simulates a DTM A&.
   In particular, show the instructions that search for the instruction code
   that matches the current state in tape 3 and the current symbol in tape


4. Then, show how to change state, change tape symbol and move left
   or right according to the instruction code.

5.2 R.E. Sets and Recursive Sets

In this section, we study the general properties of the classes of r.e. sets and

recursive sets. In particular, we present a few characterizations of r.e. sets.

Based on the work of the last section, we consider only sets over alphabet

(0, 1). We follow the notation developed in Section 4.8 and identify each

integer n with the nth string ~{o,l)(n) in (0, l}*.

First, we list two important results obtained in the last section.

Theorem 5.7 (Enumeration Theorem)

(a) A function f : ((0, l}*)k + {O,l} is partial recursive if und only if

f = C/I: for some n > 0.

(b) A set A is r. e. if und onZy if A = Wn for some n > - 0.

From the enumeration theorem, we say {Wn) is an efective enumeration

of all r.e. sets.