Problem Solving in Automata, Languages, and Complexity

5.5 Recursion Theorem

Program Pa :

el := ‘e := s; (el, el);

read(q,... ) xk);

x:+1 := e;

Program PJ :

el := ‘e := concat( “el := ““ “,

e1, cc 73 7) , >‘) 1 1 e1);

read(q,... , q);

Pf(xl,...,xkrxk+l);‘;

e := si (el, el);

read(xl,... , xk);

xk+l := e;

Pf(xl,-•,xk,xk+l);

xk+l := e;

Pf (Xl,’ l dk,xk+l);‘;

e := concat(‘el := “‘, el, “‘; )) el);

read(xl,... , x&

xk+l := e;

Pf(xl,-+k,xk+l);

( a > (b)

Figure 5.4: Self-referential programs.

261

We show the expanded version of our program, program P”, in Figure 5.4(b).

It can be checked that, after the execution of statements 1 and 2, the content

of variable e is exactly the code of program Pg.

Note that this is just an outline since we used, in program P4, the procedure

names concat and Pf instead of their program codes (see also Exercise 1 of

this section).

The recursion theorem allows us to build programs that use their own

program codes as inputs. The following are some simple applications.

Example 5.37 (a) Sh ow that there exists a constant e such that &(x) = e

for all x E (0, l}*.

(b) Show that there exists a constant e such that W, = {e}.

(c) Show that there exists a constant n such that & = &+I.

Proof. (a) Let f(x,e) = e. By the recursion theorem, there exists a constant

e such that q!+(x) = f(x,e) = e for all x E {O,l}*.

(b) Let

m,e> = { ;

.

zt;e;w;;e.

It is obvious that f is partial recursive. By the recursion theorem, there

exists a constant e such that &(x) = f(x, e). The domain of the function &

is We = {e}.

(c) IJet f(x, n) = b-L+1(x> and, th en, apply the recursion theorem to f.^0

Note that part (c) of the above example implies that no matter how we en-

code Turing machines (or machines in any reasonable computational model),

there must be two consecutive machines that compute the same function, as