258 COMPUTABILITY THEORY* (b) Show that REC srn &4.15. A set B C {O,l} is called productive if there exists a partial recursive
function 7 such that for every x:, if I& C - B then f(z) J. and f(z) E
B-WC.
(a) Show that if B is productive then B has an infinite r.e. subset.
(b) Show that if K srn A then A is productive.
(c) Conclude from (a) and (b) b a ove that a simple set cannot be a
complete r.e. set.* 16. Show that there exist two r.e. sets A and B such that A grn B and
B grn A. [Hint: construct A and B simultaneously by diagonalization.]* 5.5 Recursion Theorem
In the past few sections, we presented a few proof techniques, including dove-
tailing, diagonalization, the s-m-n theorem and reducibility, which may be
viewed as summaries of some intuitive algorithmic analysis of computable
and noncomputable objects. In this section, we introduce one more tech-
nique, the recursion theorem, which is more abstract and more powerful than
other techniques.Theorem 5.36 (Recursion Theorem) For any partial recursive function f :
((0 > 1}*)“+l + (0, l}“, there exists a constant e > -^0 such thatProof. The interesting point here is that A& is a DTM that can use its own
code e like an input. How do we get such a machine that can access its own
code as an input? The main tool here is the s-m-n theorem. We recall that,
for any y,z E (0, I}*,4
k
s:(w) (XI,-vxk) = $;+‘(Xl,.. .,xk,z).Therefore, if we set y = z, we get a machine A&l k cZ Z) ’ which simulates the
function +t+l on its own code:
Now, let us apply this to the function f. Assume that f is computed by
a DTM Mf and its machine code is el; that is, f = 42;“. From the above
observation, we see that the DTM Msl(,, el) simulates f on its code el.
Unfortunately, this index e = si (er ,Le,) ‘is not quite the index we are looking
for, since the machine M, only simulates f on el, not on e itself. In other
words, what we did above is the following: We tried to create a machine
that works just like Mf except that it also takes its own code el as the last