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.)

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$

To resolve the problem, the standard definition of computable real number in computable analysis is a program that provides rational approximations to the real, to any desired known degree of accuracy. With this version, you don't have to get the digits exactly right, if the real number is on or very close to a boundary where a large number of digits would flip from one side to the other. And the point is that now all the expected operations on real numbers — addition, multiplication, exponentiation, trigonometric functions, and so on — are all computable from the programs.