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 the petulant child algorithm, for upon finding a proof that it shouldn't do a certain thing, proceeds to do exactly the forbidden thing.

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

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

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 the petulant child algorithm, for upon finding a proof that it shouldn't do a certain thing, proceeds to do exactly the forbidden thing.

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

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 the petulant child algorithm, for upon finding a proof that it shouldn't do a certain thing, proceeds to do exactly the forbidden thing.

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