Problem Solving in Automata, Languages, and Complexity

246 COMPUTABILITYTHEORY Figure 5.2: The reduction function f cannot cross the dotline. Show that the set {(i, j) ) VVi = wj} is ...

5.4 Reducibility 247 Proof. For part (a), the identity function is a reduction function for A Lrn A for all A C C*. For pa; (b), ...

248 COMPUTABILITYTHEORY Example 5.27 Show that the set EMP = {z 1 WX = 8) is not recursive. Proof. First, we note that EMP = {z ...

5.4 Reducibility 249 Theorem 5.28 (S-m-n Theorem). For each pair of integers m, n > 0, there is a primitive recursive functio ...

(^250) COMPUTABILITY THEORY (a) If i = 0, then g(e, y, i) is the code of instructions of A& in part (i); (b) If 1 < i < ...

5.4 Reducibility 251 Then, g is partial recursive since g(y, x) = CT&C). (Recall that flK is the semi-characteristic functio ...

252 COMPUTABILITYTHEORY function-index set Ap = {z 1 P(&)} is not recursive. Similarly, the problem of determining whether a ...

5.4 Reducibility 253 (c) FIN = {Z 1 Wx is finite}. (d) REC = {z 1 W, is recursive}. (e) REG = {z 1 Wx is a regular set}. (f) REV ...

254 COMPUTABILITY THEORY be Yo For the second part of the question, we choose, any indexes such that WzO = JC and WY0 = { E REC ...

5.4 Reducibility 255 and x E FIN <q VV$ is infinite +=a (VWY) [Y > - x and Y E wi?] (‘d4(3Y) [Y > iTic and (3t) paqy, ...

256 COMPUTABILITY THEORY Exercises 5.4 1. Assume that AU B = (0, 1}* and An B # (8. Show that if A and B are re., then A srn A n ...

5.4 Reducibility 257 (b) Show that if B is an r.e. index set then nnEB Wn is also r.e. Let Cl be the class of all recursive set ...

258 COMPUTABILITY THEORY * (b) Show that REC srn &4. 15. A set B C {O,l} is called productive if there exists a partial rec ...

5.5 Recursion Theorem 259 input. However, when we apply the s-m-n theorem to create this machine, the machine code has been chan ...

260 COMPUTABILITY THEORY Program PI : Program P2 : e := ‘read(xl,... , xk); xk+l := e; Pf(xl,...,xk,xk+l);‘; read(xl,.. l , xk); ...

5.5 Recursion Theorem Program Pa : el := ‘e := s; (el, el); read(q,... ) xk); x:+1 := e; Program PJ : el := ‘e := concat( “el := ...

262 COMPUTABILITY THEORY e1 := ‘w&e( “el := “““); write(e& write( (O”‘; “); write(e& ’ ; write( ‘er := “ ‘); write(e ...

5.5 Recursion Theorem 263 From the above analysis, we conclude that A cannot be recursive. 0 The following are some more example ...

264 COMPUTABUJTY THEORY (1) Set (1: := E. (2) If f(x) < 2” then go to step (3); (3) Let x :-x + 1 and go to step (2). otherwi ...

5.5 Recursion Theorem 265 proof technique to prove that the function K(z) is nonrecursive. The theory of program-size complexity ...