17
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ Here is a use of Kleene recursion on MO: mathoverflow.net/a/402641/1946 $\endgroup$ Jan 5, 2023 at 21:53
  • 1
    $\begingroup$ Oh nice, again and again the theorem comes out and shows that no program will ever know what all the other programs do just from reading some of it's tape. $\endgroup$
    – H.C Manu
    Jan 6, 2023 at 8:39
  • 1
    $\begingroup$ Yes, I think that is a succint summary, with shades of Rice's theorem. $\endgroup$ Jan 6, 2023 at 11:39

5 Answers 5

20
$\begingroup$

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:

$\endgroup$
3
  • 1
    $\begingroup$ Is what's happening here that in the various models, a different (is this meaningful?) Turing machine is being picked out, or is the machine somehow a priori fixed and the models just disagree on its behavior? $\endgroup$ Jan 5, 2023 at 22:15
  • 3
    $\begingroup$ @DavisYoshida It is exactly the same program in the various models—we can write the program down concretely. What differs is in effect is the length of time available for computation, since in a nonstandard model of PA, one can use all the numbers including nonstandard numbers as stages of the computational process. It is at those nonstandard stages of computation where the new elements are added to the universal sequence. $\endgroup$ Jan 5, 2023 at 22:45
  • 2
    $\begingroup$ Ah that makes sense and re-reading your answer it's now clear. Thank you! $\endgroup$ Jan 5, 2023 at 23:44
12
$\begingroup$

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.

$\endgroup$
6
  • 5
    $\begingroup$ I had no idea that Turing had a wrong conception of computable number until now, very interesting stuff. $\endgroup$
    – H.C Manu
    Jan 5, 2023 at 15:35
  • 1
    $\begingroup$ He published a correction to this and several other issues in his paper, when the issues were brought to light. $\endgroup$ Jan 5, 2023 at 15:37
  • 1
    $\begingroup$ Speaking of which, were there other interesting errors like this one in the original paper? $\endgroup$
    – H.C Manu
    Jan 5, 2023 at 15:50
  • 1
    $\begingroup$ He had some errors in the details of his definition of the universal machine. Perhaps it amounts to some bugs in the first theoretical account of programming! He published corrections in 1937. See doi.org/10.1093/oso/9780198250791.003.0006 $\endgroup$ Jan 5, 2023 at 16:02
  • 2
    $\begingroup$ It should be noted that it was LEJ Brouwer who pointed out the error (and correction?). $\endgroup$ Jan 5, 2023 at 17:52
9
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Wow, I have never heard of this result before! I find this surprising given the corresponding result is very much false for sets which are computed by all non-computable oracles, or even almost all (or even all oracles in some given set of positive measure). $\endgroup$
    – Wojowu
    Jan 5, 2023 at 18:56
  • 1
    $\begingroup$ @Wojowu It is indeed delightful. Incidentally, it is currently wide open whether there is a linear order whose spectrum (= set of oracles computing copies of it) is exactly the noncomputable degrees; I believe the current best positive result (due to R. Miller) is that there is a linear order $L$ whose spectrum restricted to the degrees below ${\bf 0'}$ is the non-computable degrees. And Greenberg/Montalban/Slaman showed that SW fails for relative constructibility (under an appropriate non-triviality assumption). $\endgroup$ Jan 5, 2023 at 19:20
  • 1
    $\begingroup$ @NoahSchweber Very interesting! Thanks for sharing. $\endgroup$
    – Wojowu
    Jan 5, 2023 at 20:01
  • 1
    $\begingroup$ This result sounds very counterintuitive which makes it all the more interesting, thanks for sharing. $\endgroup$
    – H.C Manu
    Jan 5, 2023 at 21:09
7
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ I was familiar with Rice's theorem but I like the comment you made at the end about an interpretation of it. It's a kind of "no free lunch theorem" for programs/computable functions in that there is no way to extract relevant infromation about them in a computable way by using some meta-program looking at the said programs/functions. $\endgroup$
    – H.C Manu
    Jan 6, 2023 at 16:20
  • 1
    $\begingroup$ That is exactly right. $\endgroup$ Jan 7, 2023 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.