Skip to main content
3 of 4
added 1262 characters in body
Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k

Quines. One dramatic application of the Kleene recursion fixed-point theorem is the existence of Quines. These are programs that produce their own code as output.

Any Turing complete programming language will admit such a Quine. To see this, let $f(e)$ be a program that writes $e$ as output. By the recursion theorem, there is a program $e$ such that $e$ and $f(e)$ compute the same function. So $e$ is a Quine, since $e$ will give $e$ as output, as this is what $f(e)$ does.

Universal algorithm. Another dramatic application of Kleene recursion is the baby version of the universal algorithm. Namely, there is a computer program $e$, which we can write down, such that it is consistent with PA (or ZFC, whatever foundational theory you want) such that $e$ writes any given finite string as output. To find such a program, let $f$ be the computable function that on input $p$, a program, searches for a proof in PA of a statement of the form "program $p$ does not output this specific string $s$". If it finds such a proof, then $f(p)$ gives output $s$ immediately and then halts.

By the recursion theorem, there is a program $e$ such that $e$ and $f(e)$ compute the same function (and provably so). So program $e$ searches for a proof that $e$ does not output string $s$, and when it finds such a proof, it outputs string $s$ and halts. It follows that you will not be able to prove that $e$ does not have any particular $s$ as output, since if you could actually prove this, then it wouldn't be true (for the smallest instance). So it is consistent with PA that it does have any given $s$ as output.

In other words, this is a program, which we can write down, whose behavior is not determined by the PA axioms — it can be anything at all.

For the grown up version of the universal algorithm, which exhibits the universal extension property, a theorem due to Woodin, with futher work by Enayat, Blanck, and myself, see my paper, The modal logic of arithmetic potentialism and the universal algorithm.

Computable numbers. There is another application to the theory of computable real numbers. In his famous 1936 paper, Turing had defined originally that a computable real number is one for which we have a computable procedure to enumerate the decimal digits. In computable analysis today, however, we define the computable numbers as those for which we can compute rational approximations to within any desired accuracy. The issue with Turing's definition is that if you have programs for $a$ and $b$, then you cannot produce a program to enumerate the digits of $a+b$. The problem is that you can't know in general whether there will be carries forcing you to flop over a long string of digits, and so if the numbers are looking like $a=0.343434\ldots$ and $b=0.65656565\ldots$, then $a+b$ will look like $0.9999\ldots$, but you won't know whether it is actually $1.000\ldots 0002\ldots$ or $0.9999\ldots 9992\ldots$ until you find out if there is a carry. But you will never know.

One can use the Kleene recursion theorem to prove that for any proposed program, there are computable reals $a$ and $b$ for which the program gets the wrong answer for $a+b$, as I explain in my post, Alan Turing on computable real numbers.

These are three applications of Kleene recursion that I give in my book Ten proofs of Gödel incompleteness, currently in preparation.

Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k