Problem Solving in Automata, Languages, and Complexity

262 COMPUTABILITY THEORY

e1 := ‘w&e( “el := “““);

write(e&

write( (O”‘; “);

write(e& ’ ;

write( ‘er := “ ‘);

write(e&

write( ‘ ” ; ‘) ;

write(e&

Figure 5.5: A self-reproducing program.

long as the encoding of the machines admits a universal machine and satisfies
the s-m-n theorem,

Example 5.38 Write a program (in pseudo-Pascal) that, on any input,
prints its own program code as the output (this is called a self-reproducing
program).

Solution. This is just part (a) of Example 5.37 in a high-level language envi-

ronment. We can obtain a self-reproducing program by expanding the proce-

dure Pf in program Pd. We note that the program Pf here is just the program

that prints the last input as the output. In fact, the last input is just e, the

output of the procedure si (el, el). So, we may directly write the value of e

out and skip the third and fourth statements of program Pd. The resulting

program is shown in Figure 5.5. (See also Exercise 1 of this section.)^0

The recursion theorem can also simplify some proofs by the method of

reducibility. For inst ante , we can corn .bine the d .iagonalization techinique and

the recursion theorem to prove Rice’s theorem.

Example 5.30 (R evisited) Prove Rice’s theorem by the recursion theorem.

Proof. Assume that A is a nontrivial index set. Let n1 E A and no 4 A.

Suppose, by way of contradiction, that A is recursive. Then, define a function

Since A is recursive, f is partial recursive.

By the recursion theorem, there exists a constant e such that &(x) =

f(x, e). Now, consider two cases:

Case 1. e E A. Then, &(z> = f(x,e) = $&(x). However, since A is an

index set and since no 6 A, we get e $ A. This is a contradiction.

Case 2. e E A. Then, &(x) = f(x, e) = &i(x) and, hence, e E A. This is

also a contradiction.