Problem Solving in Automata, Languages, and Complexity

226 COMPUTABUJTY THEORY hard to see that for every Turing-computable function f : (C)k + C, there exists a DTM AI in M such that ...

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. Pr ...

228 COMPUTABILITY THEORY Enumeration of Partial Recursive Functions and R.E. Sets. For each string ti E (0, l}, we let A& be ...

5.1 Universal Turing Machines 229 concept of the universal Turing machine was conceived by Alan Turing well before the real digi ...

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 ch ...

5.1 Universal Turing Machines 231 where maxstate is the maximum state number of My and maxsym( y) is the maximum symbol number o ...

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 = inz ...

5.2 R.E. Sets and Recursjve Sets 233 Theorem 5.8 (Projection Theorem) Let A - C (0, l}*. The followiplg are equivalent: (Q) Ther ...

234 COMPUTABILITY THEORY (1) S([qs, qj], (a, b)) = (h, (a,b), (S,S)), for 1 < j < 6 and Cl E L-h b E Lm (a> S([qi, qt], ...

5.2 RX. Sets and Recursive Sets 235 For set D = A n B, we do not have to simulate A& and A& alternatingly, because tie n ...

236 COMPUTABILITY THEORY The above dovetailing algorithm can be simplifed by the projection theorem as follows: (Recall that (a, ...

5.2 R.E. Sets and Recursive Sets 237 one-way write-only tape, such that when it is given the empty string E as the input, M-prin ...

238 COMPUTABILITY THEORY each x = (~,t’), with t’ > t. Thus, M prints an infinite sequence of strings in A. This means that M ...

5.2 R.E. Sets and Recursive Sets 239 We will see in the next section (Corollary 5.20) that there exist sets that are r.e. but no ...

240 (b ( c COMPUTABILITY THEORY ) Construct a DTM that simulates the three DTM’s accepting sets A, B, and C by the dovetailing m ...

5.3 Diagonalization 241 Recall that AB = {zyIx~A,y~l3}. DefineA+B={n+mInE A, ti E l?}. (a) Show that if A and B are r.e. sets t ...

242 COMPUTABILITY THEORY f f 4 f 3 f 2 fl f 0 r -- r--T--~--i-- Lo:o’l’l’ -- -- .I. -- J--J-, . . . /^0 1 0 / 1 0 l/‘O I’ 0 / /^ ...

5.3 Diagonalization 243 Proof. (a) K is the complement of set A of the above example. Since K = A is not r.e;, I;;’ is not recur ...

244 COMPUTABILITY THEORY Finally, we know that f # &cn) for all n 2 0, because f(n) # &(n) (n). So, f provides us a cont ...

5.3 Diagonalization 245 To see that this construction satisfies all requirements, we first check that for each ?-I such that VI& ...