Here is another of my favorite uses of the Kleene recursion theorem. 

It arises from Turing's remarkable 1936 paper, "On computable numbers...", in which he defines Turing machines, provides a universal machine, proves the undecidability of the halting problem, solves the Entscheidunsproblem of Hilbert and Ackermann, and defines the concept of a computable real number. An incredible paper, of enduring importance, written while he was a graduate student at Cambridge. 

Nevertheless, there is a problem with his specific proposal on computable numbers. (See my [related blog post](http://jdh.hamkins.org/alan-turing-on-computable-numbers/).)

The issue is that Turing defines that a computable real number is one for which there is a computable process for enumerating its decimal digits. 

But with this notion, and if one wants to take the program as a stand-in for the computable number, to be used in further computational processes, then the problem is that most of the ordinary operations on real numbers will not be computable. 

**Theorem.** There is no computable procedure which when given input $(p_a,p_b)$ consisting of programs for enumerating the digits of reals numbers $a$ and $b$, respectively, gives as output a program $p_c$ for enumerating the digits of their sum $c=a+b$. 

The proof uses the Kleene recursion theorem. 

**Proof.** Suppose toward contradiction that there were a computable manner of taking as input any two programs $p_a$ and $p_b$ for enumerating digits of real numbers $a$,$b$, and giving as output a program $p_c$ for enumerating the digits of the real number $c=a+b$. Consider a particular instance. Specifically, let $p_a$ be the program for enumerating the digits $0.34343434\ldots$ and so on in that pattern forever. Let $p_b$ be the program which begins by enumerating the digits $0.65656565\ldots$ in that pattern, while also running the adder program on $p_a$ and $p_b$. This might seem circular, but the existence of solution to this self-reference is exactly the Kleene recursion theorem. If the adder program ever halts with some output $p_c$, then program $p_b$ begins also to run $p_c$ simultaneously, to see the initial digits of the real $c$. If that program begins with digits $1.00\ldots$ or larger,  then program $p_b$ immediately switches to digits $\ldots 22222\ldots$, that is, switch from the repeating all 65 pattern to begin at that stage with all 2s subsequently. But if the program $p_c$ begins with $0.99\ldots$, then $p_b$ switches instead at that stage from the 65 pattern to repeating all $7$ digits subsequently, $\ldots 77777\ldots$. 

Now, the main point is that because of the nature of the program $p_b$, the adder program applied to $p_a$ and $p_b$ will necessarily have the wrong answer. Namely, either the program $p_c$ never enumerates digits at all, which will be wrong since $p_a$ and $p_b$ enumerate digits and $p_c$ was the output of the adder program on $p_a$ and $p_b$, or if it does, then the output digits of $p_c$ starts with $1.\ldots$, while $a+b$ is strictly less than $1$, or it starts with $0.9\ldots$, while $a+b$ will be strictly larger than $1$. In summary, we define the program $p_b$ precisely so that it outputs digits that will violate the correctness of the output program $p_c$. So there can be no such computable adder program. $\Box$