Kleene's second recursion theorem is a fundamental result in computability theory that allows for the construction of self-referential programs. In its classical form, the theorem states that for any partial recursive function $\psi$, there exists an index $e$ such that the function $\varphi_e$ behaves as $\psi(e, \bar{x})$. A Quine is a specific corollary of this theorem: by setting $\psi$ to the identity function, one can find an index $e$ that represents a program which, when executed, outputs its own source code. While often discussed in abstract terms, formalizing this construction provides a clearer path to understanding how self-reference is structurally supported by the underlying logic of computation.

Mathematical notation showing the equivalence of a function index and its transformed version.
A formal representation of the fixed-point property where a function index is equivalent to its transformation.en.wikipedia.org

This image illustrates the core mathematical property of Kleene's second recursion theorem, where a function index $e$ is found such that $\varphi_e$ behaves as the desired property.

Mathematical notation for a fixed point in a recursive function sequence.
The notation $\varphi_n \simeq \varphi_{F(n)}$ represents the fixed point used to construct a Quine.en.wikipedia.org

This specific notation directly supports the article's explanation of how a Quine is a corollary of the theorem by finding a fixed point.

To move from abstract theory to a concrete implementation, one can adopt a functional programming perspective. In this model, a language $L$ is assumed to have a type $\mathsf{AST}$ for syntax trees and a quasi-quoter $\mathsf{q}$ that can internally perform quotations. Under these assumptions, the theorem can be stated as: for any type $T$ and any property $P : \mathsf{AST} \rightarrow T$, there exists a term $t : T$ such that $P \lceil t \rceil = t$. The proof involves constructing a term $d$ that captures the property $P$ and then finding a fixed point $t := d \lceil d \rceil$. This approach demonstrates that the theorem is not just about Quines, but about finding fixed points for any syntactic property, such as a program that outputs its own size or its own pretty-printed source code.

Implementing this in the untyped lambda calculus requires representing the language's own syntax using Church encodings. Because the untyped lambda calculus is expressive enough to handle tree-like data, one can define an AST representation where variables, applications, and lambda abstractions are encoded as lambda abstractions themselves. The most complex component is the quasi-quoter, which must be defined as a fold over the tree structure of the AST. By translating these equations into Church encodings, one can construct a Quine in de Bruijn notation. This formalization highlights a significant trade-off: while the untyped lambda calculus simplifies the proof by removing type constraints, it requires a rigorous, manual construction of the AST and quotation mechanisms to achieve the same result as higher-level functional languages.