Here we give an illustrative proof of Kleene’s recursion theorem, a fundamental theorem in computability/recursion theory. The proof is so simple it can be stated in few lines. On the other hand, the proof is a beauty in itself (after you get hold of it). Without further ado, we will first state the preliminary definitions/lemmas/theorems and then give the formal statement.
The words recursive and computable mean the same thing, and can be used interchangeably.
A partial function is defined on only some inputs. A total function is defined on all inputs. Here, inputs are natural numbers. If a function is not defined on some input , we say that diverges, denoted by . Otherwise, if we can compute , we say that converges, denoted by .
Every partial computable function is computable by a Turing Machine (TM). This is the famous Church-Turing Thesis. The inputs on which this function is undefined, the Turing Machine will produce no answer. Hence there exists a TM program for every partial function. The entire description of this program can be uniquely converted to a natural number. Thus the partial computable function which is computed by the TM program with description is denoted by , where is a natural number.
Consider any partial recursive function . The S-m-n theorem (in its simplest form) tells us that there exists a total computable function such that for all . In other words, it is possible to find (by a TM) a partial recursive function which has the same input-output mapping as for all inputs . You can think about it as hard-wiring one or more input-arguments of any function into its index.
Now we are ready to state the recursion theorem.
Kleene’s Recursion Theorem tells us that for every total computable function which takes a natural number as input and gives another natural number as output, there exists a particular input such that the two partial computable functions and have the same input-output characteristics.
In other words,
- Pick any computable function that is total.
- Then, there exists some natural number , such that
- If we grab the two partial functions and , we will see that
- Wow! They have the same input-output mapping for all inputs, that is,
- If diverges for some , so does .
- If converges for some , so does and moreover, .
This is the same as saying that every total computable function has an input element such that the two partial functions indexed by and will behave identically on all inputs. In this sense, is called the fixed-point for the total computable function .
The proof is elegant and short. However, it contains (like most recursion theory proofs) self-references and therefore sometimes hard to visualize for a beginner. Below we will outline the proof presented to our class lecture by Professor Johanna Franklin.
Step 1. Consider a total, one-to-one function with one input. We will define this function later. This function maps the given natural number to another natural number.
Step 2. Consider any total computable function , which also maps a given natural number to another natural number.
Step 3. Now consider the composition of , that is, the result of successively applying and on some input. Clearly, since both and are total, the composition will also be total. Let be the total function that computes this composition. Therefore, for all . Note that is a fixed number which must exist although we do not know its exact value. Also note that since is total, it follows that .
Step 4. Let . Since is a total function, such an must exist. Now we have .
Step 5. Now we will define a partial function on two inputs, as follows. First, we will evaluate (remember that is an input to our function ). If converges to some value, say, , then gives the same output as . Note that since is partial, this output may or may not converge. Otherwise, if , then our function diverges. This description is given as follows:
Step 6. Now it is time to define the total one-to-one function mentioned at Step 1. We will do it as follows. We will take the partial function defined in previous step, then use the S-m-n theorem to show the existence of another partial function which has identical input-output behavior as .
Therefore, is a function which maps a natural number to another natural number. Since the parameter of the function can be any natural number, is defined for all inputs, and hence total. Moreover, as S-m-n theorem tells us, is computable as well.
Step 7. Now we have all the pieces of the puzzle. Here we are interested at only one particular number, namely from Step 3. At Step 3 we showed that is total, and hence . Therefore, for any input parameter , we have the following.