**(Kleene – Recursion Theorem)** For any computable function

there exists an with .

**Proof:**

We define a partial recursive function by . By s-m-n theorem or parameter theorem, we can find a recursive function such that

for .

Let , choose then we have

Using recursion theorem, we have a beautiful proof for Rice’s Theorem.

Let be a class of partial recursive functions. Set is recursive, if and only if or contains all partial recursive functions.

**Proof:**

or is trivial. We proof the case and .

Denote .

Exist and . If is recursive, the following function is also recursive:

By recursion theorem, . We consider 2 cases:

- , by index property we have , so by the definition of . We get contradiction.
- , by index property , so by the definition of . Again we arrive to contradiction.

**Functionception**

Why’s recursion theorem interesting? A typical application of recursion theorem is to find a function that can print itself. Let’s say *print(*program*)* is that function. The output of *print(*program*)* is not **program** but the function that excuses *print(*program*)*. In other words, we could ask if there is a function which can be self-conscious. I like to call it function-ception, which can be related to inception: *does one know that he is dreaming in his dream?*

Kleene recursion theorem offers an answer to our question: there is a function-ception, or a program that can print itself. We’ll construct such that function.

Let , is the projection function .

By s-m-n theorem, there is total recursive function such that . Let . Apply Kleene recursion theorem, there is a number such that .

For each :

My work here is done!

**How many fixed points does a recursive function have?**

Intuitively, we can see that a (total) recursive function has infinite fixed points. Recall the proof for Kleene recursion theorem, when we choose . There is an infinite number of having that property. Analogically , there is an infinite number of ways to implement (write code) a function (by adding comments, using different variable names, …)

Now let’s work on some exercises using recursion theorem.

**Lemma**: There is a number , such that

**Proof**:

We need to find a function that is only defined for input and undefined on the rest of natural numbers

I’m doing this in reversing way (how my thought leads me to the solution). By recursion theorem, .

Let is the function that it is only defined for such that . Such an can be constructed as following:

My work here is done. There is an index such that , by s-m-n theorem there is a total recursive function . Let , and the last step is trivial.

**Lemma**: There is a number , such that

**Proof:**

With the same line of proof for the previous lemma, we only need to construct a partial recursive function . One can easily recognize is a projection function