260 COMPUTABILITY THEORY
Program PI : Program P2 :
e := ‘read(xl,... , xk);
xk+l := e;
Pf(xl,...,xk,xk+l);‘;
read(xl,.. l , xk);
xk+l := e;
pf(~l,-,xk,xk+l);e .- .- 'e := “read(xl,... , xk);
xk+l := e;
Pf (21, l l l ,xk,xk+l);” ;
read(xl,... , xk);
xk+l := e;
Pf(%-•,xk,xk+l);‘;
read(xl,.. ., xk);
xk+l := e;
Pf (Xl, l ’ l $krxk+l);( > a (b)
Figure 5.3: Two attempts for a self-referential program.
of directly creating the program code e does not work. For instance, if we
change the first statement of program PI to define e as the program code of
the whole program PI, including the first statement, it still does not work
as the new statement one has been changed. This new program Pz is shown
in Figure 5.3(b). (W e o f 11 ow the convention that the double quotes “ and
” within two enclosing single quotes really denote the single quotes ‘ and ‘,
respectively; e.g., ‘ab“cd”’ denotes the constant string of length 6: ab’ cd) .)
Now, let us try to use the idea of the proof of Theorem 5.36 to construct
the program Pe. As we discussed in the proof, this program Pe has three
components: the program Pf, the program Ps which computes the function
si, and the code el. Here, el is the constant string that includes the codes of
both Pf and Ps. Thus, based on this idea, we come up with the program P3
of Figure 5.4(a).
But, what exactly is the function si (el, el) in the high-level language form?
Suppose that u is a program code and v is a string. Then, s~(u, V) outputs
the program code of the following form (assuming that the (Ic + 1)st input is
called el):
el := w;
u;Therefore, the correct program code e = si(el, el) should be the concatena-
tion of four strings:
(1) The constant string ‘el := “‘,
(2) The string el (the content of el, not the name ‘el’),
(3) The constant string “‘;’ and
(4) The string el.