What are some interesting applications/corollaries of Kleene's Recursion theorem?

Question

Lately I became very interested in the theory of computability and a fundamental early result you learn is the Recursion Theorem also known as the Fixed point theorem. At first sight you can see it's immediate usefulness in that it allows you to define computable functions using their own indices. A nice and simple application of it is the fact that we can compute infinitely many fixed points for any computable function. I know however that there are many interesting and clever applications of it and my question is

What are some of your favorite uses of this theorem?

Answer 1

My favorite use of the Kleene recursion theorem is the universal algorithm.

In the baby form, consider the program $e$ that (on any input) undertakes the following process: it looks for a proof from PA of a statement of the form: "the output of program $e$ does not conform exactly with an explicitly given finite list of input/output pairs $(a_0,b_0),\ldots,(a_n,b_n)$." If such a proof is found, then program $e$ immediately proceeds to operate in conformance with that table of values. This is an instance of the petulant child algorithm, for upon finding a proof that it shouldn't do a certain thing, the program proceeds to do exactly the forbidden thing.

The program $e$ was defined in a self-referential manner, for it is searching for a proof about itself. And so the existence of such a program $e$ follows from the Kleene recursion theorem, as follows. For each program $e$, let $f(e)$ be the program that computes as above, searching for proofs about program $e$. By the recursion theorem, there is a program $e$ such that $e$ and $f(e)$ provably compute the same function. So this $e$ is searching in effect for proofs about itself.

The main observation to make about this form of the universal algorithm is that you cannot refute any particular finite behavior for this program, because if you could, then there would be a proof that it didn't conform with that behavior. But in this case, it WOULD have the behavior, because of how it is defined.

And because you cannot refute any particular behavior, it follows that it is consistent with PA that it has any desired finite behavior. The universal algorithm can in principle compute any function whatsoever, if only it is run in the right universe.

The full version of the universal algorithm theorem, due originally to W. Hugh Woodin, shows moreover that one can arrange a universal extension property.

Theorem. (Universal algorithm) There is a Turing machine program $e$ such that

1. PA proves that $e$ enumerates a finite sequence.
2. In the standard model, $e$ enumerates the empty sequence.
3. In any model $M\models\text{PA}$, if the sequence enumerated is $s$, then for any finite extension $t\supseteq s$ in $M$, there is an end-extension $M\subseteq N\models\text{PA}$ such that in $N$, the program $e$ enumerates $t$.

In other words, no matter the current finite behavior of the function, for any desired further behavior, you can find an alternative universe in which it has exactly that behavior.

See my paper:

• Joel David Hamkins, The modal logic of arithmetic potentialism and the universal algorithm, 2018. arxiv:1801.04599

Answer 2

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.

Answer 3

Kleene’s amazing second recursion theorem by Moschovakis contains:

A list of some (18) of the most significant applications of the Kleene's Second Recursion Theorem, in a kind of “retrospective exhibition” of the work that it has done since 1938. [...] These were selected because of their foundational significance and the variety of ways in which they witness how the recursion theorem is used.

A talk by Moschovakis gives an overview.

Answer 4

I like Wehner's version of the Slaman-Wehner construction.

Theorem. There is a family of sets which can be enumerated by every non-computable oracle, but is not computably enumerable.

The family is $\{ \{n\}\oplus F : \text{$F$ is a finite set with $F \neq W_n$}\}$, where $(W_n)_{n\in\omega}$ is the standard listing of c.e. sets. The part that makes use of the recursion theorem is showing that the family is not computably enumerable.

Proof. Suppose $(A_i)_{i\in\omega}$ is an enumeration of the family. Design the computable function $g$ which, on input $n$, searches for a set of the form $\{n\}\oplus F$ in the family and then outputs a c.e. index for $F$. So $W_{g(n)} = F$. But $F \neq W_n$, by construction, and thus $g$ violates the recursion theorem.

Answer 5

Here is a further example, which I find to be one of the rather more philosophically profound results in computability theory. Namely, Rice's theorem.

The theorem states, at bottom, that no nontrivial property of a computable mathematical structure is computable in a well-defined manner using as input only the programs that provide those structures. We cannot tell definitively anything about a structure from its program, in a manner that works for all such programs.

Theorem. (Rice's theorem) Suppose that $\mathcal{A}$ is any family of subsets of $\newcommand\N{\mathbb{N}}\N$. If there is a computable process for deciding on input $e$, a program index, whether the set $W_e$ enumerated by $e$ is in $\mathcal{A}$, then either $\mathcal{A}=\varnothing$ or $\mathcal{A}=P(\N)$.

The proof uses the Kleene recursion theorem.

Proof. Suppose there were such a computable decision process $q$ for deciding membership in $\mathcal{A}$, yet that $\mathcal{A}$ is nontrivial in that some $W_r\in\mathcal{A}$ and some other $W_s\notin\mathcal{A}$. Let $e$ be the program that performs the following process. First, it runs the decision program $q$ on $e$ itself. We use the Kleene recursion theorem to know that there is a program $e$ doing this part in conjunction with the rest of the algorithm I describe now. If $q$ says that $W_e$ is in $\mathcal{A}$, then $e$ immediately starts behaving like program $s$, so that $W_e=W_s$, which is not in $\mathcal{A}$. And if $q$ says that $W_e$ is not in $\mathcal{A}$, then program $e$ immediately starts behaving like $W_r$, so that $W_e=W_r$, which is in $\mathcal{A}$. So in either case, $q$ has gotten the wrong answer on $e$. So there can be no such decision algorithm $q$ for a nontrivial $\mathcal{A}$. $\Box$

The main moral is that the only thing you can really know about a computably enumerable set from its program is what you get by running the program. But if the program takes too long to do anything sufficient for you to decide whether it has the property or not, then you will not be able to decide correctly in all instances.