5.5 Recursion Theorem 265
proof technique to prove that the function K(z) is nonrecursive. The theory
of program-size complexity has many interesting applications to computabil-
ity theory and computational complexity theory. The reader is referred to Li
and Vitanyi [1997] for further study.
Exercises 5.5
- If we look at the self-reproducing program of Figure 5.5 (and program P4
of Figure 5.4(b)) more carefully, we can see that it is still not completely
correct, because all the double quotes in the program are printed as
single quotes in the output. More precisely, each double-quote in the
right-hand side of the first assignment statement “ei := l l 0” is stored in
el in the form of a single quote and so the third statement “write(e&”
prints the right-hand side of the first statement with each double-quote
replaced by a single quote. Fix this problem to make the program print
exactly its own program code. - Write a computer program (in your favorite high-l1
prints the reversal of its own code. - Write a computer program (in your favorite high-l
reads an input n and prints its own code n times.
eve1 language) that
eve1 language) that
- Write a computer program (in your favorite high-level language) that
reads an input x and outputs 1 if x is exactly its own program code,
and outputs 0 otherwise. (This is called a self-recognizing progrum.) - Prove that there exists an integer e > 0 such - that we = we ‘1 U we+l.
- Prove that for every recursive function f there exists a constant e such
that 4j(e) = A* - Prove that there exists a recursive function f such that &,e(f(e~~(~) =
+j(&) for all X. - Prove that there exist two integers m. # n such that W, = {n} and
wn = {r-n}. [Hint: Note th a t in the proof of the s-m-n theorem, the
function sh(e, y) satisfies the property s&(e, y) > y.] - (a) Prove that the s-m-n theorem can be improved so that each sk is a
one-to-one function in the sense that if el # e2 then s&(el, yi,... ,
Y~)#S~(e2,Yl,*~~,Yn)fo~allYl,**.,Y~EN.
(b) Show that for any partial recursive function g and any constant
n, there exists a constant e > n such that &(z) = g(z,e). - Does there exist an integer m. such that W, = {x] @&z) is defined}?
Does there exist an integer n such that W, = { ~1 &(n) is undefined}?
Prove your answers.