# Constructing a Quine Using Kleene's Second Recursion Theorem Formalizing self-replicating programs through lambda calculus and recursion theory. - **Source:** [Hacker News: Front Page](https://brifing.si/source/b07aa772-b1a0-4a76-aa18-719c6f9e2dde) - **Published:** 2026-10-31 - **Topic:** [Software & Engineering](https://brifing.si/c/engineering) - **Original article:** - **On Brifing:** https://brifing.si/s/aa31f662-f9e2-41ed-b441-02e6004e5736 ## Formalization as Insight Formalization is often dismissed as mere transcription, yet it serves as a powerful tool for structural clarity. By forcing the mathematician to define terms precisely, it reveals the underlying logic of complex theorems. This approach transforms abstract concepts into concrete, verifiable structures, moving beyond the hand-wavy explanations common in traditional computability theory. ## Kleene's Recursion Theorem Kleene’s second recursion theorem states that for any partial recursive function, there exists an index e such that the function behaves as a fixed point. In the context of Quines, this index represents the program's own source code. This mathematical foundation allows a program to output its own representation upon execution. ## Beyond Reductionist Approaches Traditional computability theory often relies on reductionism, treating all discrete structures as natural numbers through tedious encodings. This approach frequently leads to hand-waving, as presenters avoid low-level details. By contrast, proof theory emphasizes the significance of structure, suggesting that how we formalize systems directly impacts our understanding of their computational content. ## Lambda Calculus Advantage The untyped lambda calculus serves as an ideal model for exploring these structures due to its simplicity and expressivity. It allows for non-trivial programming tasks while maintaining a minimal set of features. This makes it particularly suitable for implementing self-reflective languages where the system must manipulate its own abstract syntax tree representations. ## Typed vs Untyped Perspectives While the recursion theorem is often presented via partial recursive functions, considering a typed presentation draws valuable connections to other logical results. In the untyped lambda calculus, these types effectively fall away as moral types. This perspective allows us to apply the theorem broadly, finding fixed points for various syntactic program properties. ## Generalizing the Fixed Point The theorem extends beyond simple Quines by allowing us to find fixed points for any syntactic property. By setting the function P to identity, we generate a standard Quine. However, using P as a size or pretty-print function produces programs that output their own size or formatted source code, respectively. ## Logic and Incompleteness When applied to total languages like higher-order arithmetic, the recursion theorem links directly to fundamental logical results. Specifically, it provides the diagonal lemma, which is the key ingredient for both Gödel’s first incompleteness theorem and Tarski’s undefinability theorem. These connections demonstrate the deep, functional nature of self-referential systems within formal logic. ## Implementation via Church Encodings Implementing these concepts requires an AST representation of the language, which is easily achieved using Church encodings. The untyped lambda calculus represents variables, applications, and abstractions as lambda terms. A quasi-quoter, acting as a fold over the tree structure, then enables the construction of the self-referential term within the language itself. ## Practical Formal Verification The construction was successfully reasoned about and implemented in the Rocq proof assistant. The resulting Quine, expressed in de Bruijn notation, demonstrates the feasibility of formalizing high-level recursion theorems. This exercise confirms that structured formalization is not just a theoretical pursuit but a practical method for verifying complex self-referential computational behaviors. ## Sources covering this story - https://emarzion.github.io/KSRT/ — --- _Summary written by Brifing from the original reporting. Copyright in the original article belongs to its publisher; read the full piece at the link above._