Problem Solving in Automata, Languages, and Complexity

5.5 Recursion Theorem 259

input. However, when we apply the s-m-n theorem to create this machine,

the machine code has been changed from el of A@ to e = sk(er , el) of the

new machine. So, the last input el is no longer its own machine code.

To fix this problem, we need to make two adjustments: First, we need

to compute the new machine code e from el, and then simulate A.@ on e

instead of e 1. This can be done by simulating a DTM A&’ that computes the

function sk to get e = si(er,er). Next, we note that now the new machine

has been changed again (it now needs to simulate both A4f and &!‘), and so

the original code el has to be modified accordingly. What is the correct new

er? We note that the output e = sL(el, el) is to be used as the last input

to A@. Therefore, el should be the code of a machine that computes the

function f(zl,.. l 7 Xk, s;(xk+l, xk+l))*

In summary, the new DTM A4e works as follows:

(1) It contains three components: the code of DTM A4f that computes f,

the code of DTM A4” that computes sk, and the constant el.

(2) It first computes its own code e by simulating A4’ on (el, el).

(3) It then simulates A4f on inputs (xl,... , xk, e).

The following is the formal proof using the above ideas:

First, by the enumeration theorem, there exists a constant el such that

4y(xl, l l l f Xk, %+1) = f(x1, l l l , Xk, s;(xk+l, xk+l)).

Let e = si (er , el). Then, we verify that e satisfies the requirement:

It is interesting to note that the above proof does not rely on specific
properties of the Turing machine model. It works for any computational
model in which the enumerability theorem and the s-m-n theorem hold true.
To demonstrate this fact, and also to get more insight into the proof of the
recursion theorem, let us prove it in the context of a more practical high-level
programming environment (using a pseudo-Pascal language).
The question is to find, from a given program Pf , a new program Pe that, on
input (xl,... , xk), can generate its own program code e and simulate program
Pf oninput (xl,..., x:F,, e), treating e as a character string. Our first attempt
of such a program PI is to let e be the code of a program that simulates Pf
on (xl,..., xk, e), as shown in Figure 5.3(a). (In program PI, we use single
quotes ‘ and ’ to define a constant string; for example, ‘string’ denotes the
constant string of length 6: string.) Note, however, that the constant e
defined in the first statement of program PI is not the correct program code
of itself since it does not include the first statement. Since the real code of
the program needs to refer to itself (i.e., it is self-referentid), this approach