Recursion Theorem

(Kleene – Recursion Theorem) For any computable function
f there exists an e with \phi_e = \phi_{f(e)}.

Proof:

We define a partial recursive function \theta by \theta(u,x) = \phi_{\phi_u (u)} (x) . By s-m-n theorem or parameter theorem, we can find a recursive function d such that

\forall u: \phi_{d(u)}(x)=\theta(u,x) for \forall x.

Let \phi_v = f \circ d, choose e=d(v) then we have

\phi_e(x) = \phi_{d(v)}(x) = \theta(v,x) = \phi_{\phi_v (v)} (x) = \phi_{f \circ d(v)}(x) = \phi_{f(e)}(x)

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

Let C be a class of partial recursive functions. Set \left\{e | \phi_e \in C \right\} is recursive, if and only if C = \emptyset or C contains all partial recursive functions.

Proof:

C = \emptyset or C = \mathbb{N} is trivial. We proof the case C \ne \emptyset and C \ne \mathbb{N}.

Denote  S = \left\{e | \phi_e \in C \right\}.

Exist e_0 \in S and e_1 \in \neg S. If S = \left\{e | \phi_e \in C \right\} is recursive, the following function is also recursive:

f(x) = \left\{ {\begin{array}{*{20}c}  {e_0 : x \in \neg S} \\  {e_1 : x \in S} \\  \end{array}} \right.

By recursion theorem, \exists e': \phi_e' =\phi_{f(e')}. We consider 2 cases:

  1. e' \in S, by index property we have f(e') \in S, so e_1 \in S by the definition of f. We get contradiction.
  2. e' \in \neg S, by index property f(e') \in \neg S, so e_0 \in \neg S by the definition of f. 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 \phi_e = \pi_1^2, \pi_i^n is the projection function \pi_i^n(x_1,...,x_n) = x_i.

By s-m-n theorem, there is total recursive function s(e,x) such that \phi_{s(e,x)}(y)=\phi_e(x,y).  Let g(x) = s(e,x). Apply Kleene recursion theorem, there is a number n such that \phi_{g(n)} = \phi_n.

For each x: \phi_n(x) = \phi_{g(n)}(x) = \phi_{s(e,n)}(x) = \phi_e(n,x) = \pi_1^2 = n

My work here is done!

How many fixed points does a recursive function f have?

Intuitively, we can see that a (total) recursive function f has infinite fixed points. Recall the proof for Kleene recursion theorem, when we choose v: \phi_v = f \circ d. There is an infinite number of v 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 n \in \mathbb{N}, such that W_n = \left\{ n \right\}

Proof:
We need to find a function \phi_n that is only defined for input n and undefined on the rest of natural numbers \mathbb{N}-{n}

I’m doing this in reversing way (how my thought leads me to the solution). By recursion theorem, \exists n : \phi_n(x) = \phi_{f(n)}(x) = \phi_{s(e,n)}(x) = \phi_e(n,x).

Let g(x,y)  is the function that it is only defined for (x,y) such that x=y. Such an g(x,y) can be constructed as following:

g(x,y) = \left\lfloor {\frac{1}{{\neg sign\left( {\left| {x - y} \right|} \right)}}} \right\rfloor

My work here is done. There is an index e such that \phi_e(x,y) = g(x,y), by s-m-n theorem there is a total recursive function s: \phi_{s(e,x)}(y) = \phi_e(x,y). Let f(x) = s(e,x), and the last step is trivial.

Lemma: There is a number n \in \mathbb{N}, such that \phi_n = \lambda x[n]
Proof:

With the same line of proof for the previous lemma, we only need to construct a partial recursive function g(x,y) = x \forall y. One can easily recognize g(x,y) is a projection function \pi_1^2