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$