|
|
|
|
|
|
 ; input (b) |
|
|
|
|
|
|
|
|
Thus, x is treated as a datum which s stores in the "text" of the program p. This may seem a very innocuous property, but is in fact extremely powerful. For example, one can characterize the acceptable programming systems as exactly those programming systems for which the s-m-n theorem holds. The s-m-n theorem will be a key tool in the technical work of this book. Here is a simple application that establishes another property of acceptable programming systems. |
|
|
|
|
|
|
|
|
2.2 Lemma There is a one-one, strictly increasing, recursive function  such that, for all p and x, |
|
|
|
|
|
|
|
|
Thus, p, pad(p, 0), pad(p, 1), . . . is an infinite, strictly increasing sequence of programs for j p. |
|
|
|
|
|
|
|
|
Proof: Suppose i is a j -program such that, for all p, x, and y, j (p, x, y) = j (y). (Since  is partial recursive, such an i must exist.) Define  . By Theorem 2.1 pad is one-one, strictly increasing, and, for all p, x, and y, |
|
|
|
|
|
|
|
|
Thus, pad(·, ·) is as required. |
|
|
|
|
|
|
|
|
Another important property satisfied by acceptable programming systems is Kleene's recursion theorem. This theorem provides us with the means to construct programs that self-referentially refer to their own program text. Here is the theorem's formal statement. |
|
|
|
|
|
|
|
|
2.3 Theorem (Kleene's Recursion Theorem) For each partial recursive y there is a j -index e such that, for all x, |
|
|
|
|
|
|
|
|
Moreover, one can uniformly, effectively find such an e. That is, there is a recursive function r such that, for each p,  . |
|
|
|
|
