- Introduction
- Kleene, Classical Perspective
- Models of Computation
- Kleene, Functional Programming Perspective
- Building a Quine in Untyped Lambda Calculus
- Putting It All Together
- References
It is a well-known fact that the beingness of Quines are a consequence of Kleene’s 2nd recursion theorem. I was inquisitive concerning how uncomplicated or difficult it was to use this building in practice, so I decided to try to formalize it.
One of the virtues of formalization is that it naturally motivates the mathematician to construction their definitions and proofs in a clearer and additional concise fashion. The ache of a clunky definition or ill-structured disagreement is really felt, and so the goals of expedient proofs and well-structured proofs frequently align. Far from being a mechanical chore, the act of formalization can really be a origin of understanding and ingenuity (incidentally, this is why I think the famous perspective of ceremonial verification as a uncomplicated exercise in transcription misses the mark).
With this in mind, I hoped that I could discover or create a spotless formalization that could shed several ray on a theorem that I was lone acquainted alongside on fairly hand-wavy terms. During my search, I was fortunate adequate to reveal this outstanding preprint that laid out how to execute this building in the untyped lambda calculus. For the remainder of this article I volition diagram out the evidence from this preprint and recommendation several motivation for why we power chose to current the theorem this way.
The customary display of the recursion theorem assumes we are operating alongside an productive numbering of the partial recursive functions $\lbrace \varphi_i \rbrace_{i \in \mathbb{N}}$. We can afterward province the outcome as follows:
Theorem (Kleene’s second recursion theorem, traditional computability theoretic version)
Let $\psi$ be an $n+1$-ary partial recursive function. Then there is an indicator $e$ specified that
\[\psi(e,\bar{x}) \simeq \varphi_e(\bar{x})\]
Quines autumn out as a corollary whenever we obtain $\psi$ to be the identity, giving us
\[e = \psi(e) \simeq \varphi_e()\]
If we squint we can ideate this to be a Quine. Intuitively, the indicator $e$ is a depiction of the function $\varphi_e$, and thus $\varphi_e$ is a program that on no inputs outputs $e$, its own “source code”.
Traditional presentations of computability theory lean to clasp a reductionist outlook anywhere all discrete structures (pairs, lists, syntactic objects, etc.) are fair natural numbers. This necessitates many tedious encodings whose particulars the presenter would favor to not mention, and thus we get a lot of hand-waving.
This kind of display is understandable to an extent. If you are lone curious in arriving at deep/advanced results, it makes awareness that you would not desire to discarded too much period alongside the low-level particulars when, following all, “all these models of computation are equivalent” anyway. However, this kind of method runs the hazard of engendering a kind of nihilism alongside regard to ceremonial systems. All systems are likewise arbitrary, ugly, etc. so why annoy equal studying them in detail?
There is a subfield that takes matters of construction in ceremonial systems additional seriously: Proof theory. One of the big takeaways I received from evidence theory is that there can be important satisfied established in the way we construction our ceremonial systems. So, returning to computability theory, it is suitable that our hunt for a example that takes construction seriously, we attain at the most proof-theoretic example of computation, the lambda calculus.
Even although we volition ultimately activity in the untyped lambda calculus, it is helpful to regard a typed display of the recursion theorem. We volition see that using explicitly types draws connections to another results, but the disagreement motionless applies to the untyped case, anywhere the types autumn distant as “moral types” (for instance, we can motionless conversation of functions $\mathbb{N} \rightarrow \mathbb{N}$ in untyped lambda calculus equal although the types aren’t really there).
We volition assume we are operating in a functional tongue $L$ that is capable of self-reflection. In particular:
- It has a category $\mathsf{AST}$ of syntax trees that portray $L$-expressions:
- If $t$ is a term afterward we volition obtain $\lceil t \rceil : \mathsf{AST}$ to signify its quotation.
- The constructor for function use volition be stated by the infix $\cdot$ and so the following equation is valid: $ \lceil t_1 t_2\rceil = \lceil t_1 \rceil \cdot \lceil t_2 \rceil $
- It has a quasi-quoter that is capable of internally performing quotations whenever the expression is itself a quote. Specifically, there is a term $\mathsf{q} : \mathsf{AST} \rightarrow \mathsf{AST}$ specified that for any term $t$ we have that $\mathsf{q} \lceil t \rceil = \lceil \lceil t \rceil \rceil$. In another words, $\mathsf{q}$ is a function that turns single-quoted expressions into double-quoted expressions.
With those assumptions, Kleene’s theorem can be stated as follows:
Theorem (Kleene’s second recursion theorem, functional version)
Let $T$ be a category and $P : \mathsf{AST} \rightarrow T$. Then there is a term $t : T$ specified that $P \lceil t \rceil = t$.
Proof.
Take $d : \mathsf{AST} \rightarrow T := \lambda e. P (e \cdot \mathsf{q} \hspace{2pt} e)$. Then our fixpoint expression is $t := d \lceil d \rceil$:
\[\begin{aligned} t &= d \lceil d \rceil \\ &= (\lambda e. P (e \cdot \mathsf{q} \hspace{2pt} e)) \lceil d \rceil \\ &= P (\lceil d \rceil \cdot \mathsf{q} \lceil d \rceil) \\ &= P (\lceil d \rceil \cdot \lceil \lceil d \rceil \rceil) \\ &= P \lceil d \lceil d \rceil \rceil \\ &= P \lceil t \rceil. \end{aligned}\]
As before, we get Quines whenever we obtain $P$ to be the identity, but we see that the theorem can be additional broadly applied to discover fixed-points for any kind of “syntactic” asset of a program. For example, taking $P := \mathsf{size} : \mathsf{AST} \rightarrow \mathbb{N}$ produces a program that outputs its own size, and letting $P := \mathsf{pretty}\text{_}\mathsf{print}: \mathsf{AST} \rightarrow \mathsf{string}$ yields the additional acquainted form of a Quine as a program printing out its own origin code in a content format.
Some Logical Digressions
Even although the recursion theorem is frequently presented in the environment of the partial recursive functions, it have to be noted that our evidence does not assume $L$ is Turing complete. Indeed, we discover crucial connections to another areas of logic whenever we regard Kleene in the environment of a particular category of total languages: the term languages of arithmetic systems.
Imagine we are operating in several kind of higher-order arithmetic alongside a category of propositions $\mathsf{Prop}$. This could be a evidence aide akin Rocq itself, for example. If we obtain $T = \mathsf{Prop}$ we have ourselves a extremely functional display of the diagonal lemma, the key component to the two Gödel’s archetypal incompleteness theorem and Tarski’s undefinability theorem. Here’s how those two appear in this setting:
-
Gödel: Take $\mathsf{Prov} : \mathsf{AST} \rightarrow \mathsf{Prop}$ to be our provability predicate. If we set $P := \neg \circ \mathsf{Prov}$ afterward the recursion theorem gives us several $\phi$ specified that
\[\phi = \neg \mathsf{Prov} \lceil \phi \rceil\]This $\phi$ is the Gödel sentence.
-
Tarski: Suppose $\mathsf{Tr} : \mathsf{AST} \rightarrow \mathsf{Prop}$ is a fact predicate, definition that the fact scheme \(\mathsf{Tr}\lceil \phi \rceil \iff \phi\) holds for all $\phi$.
Take $P := \neg \circ \mathsf{Tr}$. Then there is several $\phi$ with
\[\phi = \neg \mathsf{Tr}\lceil \phi \rceil \iff \neg \phi\]
We have seen from the evidence outlined complete that lambda calculi guide to a fairly spotless and concise evidence outline. What makes the untyped lambda calculus particularly appealing is that the tongue is extremely uncomplicated alongside few features, during additionally being expressive adequate to do non-trivial programming tasks in it. For a project specified as this anywhere we need to execute the tongue inner itself, this blend of qualities is essential.
The archetypal item we need to execute the evidence complete is an AST depiction of the tongue itself. Fortunately, the untyped lambda calculus can effortlessly grip specified treelike data alongside Church encodings.
The untyped lambda calculus consists of variables, applications, and lambda abstractions:
\[\Lambda ::= v | \Lambda \Lambda | \lambda v. \Lambda\]
These three constructors display up in the encoding as three lambda abstractions $\lambda v a l. \cdots$, anywhere the build of the term is built up from $v, a, l$ in a manner that immediately mirrors the construction of the term. For example, if we desire to citation the term $\lambda x y. y x$ we get this:
\[\lceil \lambda x y. y x \rceil = \lambda v a l. l (l (a (v \underline{0}) (v \underline{1})))\]
($\underline{0}$ and $\underline{1}$ are the Church numerals of the variables’ de Bruijn indices).
The final item we need is a quasi-quoter. This is certainly the hairiest part but it not too bad formerly you have the particulars figured out.
If we were to compose out the equations for a quasi-quoter in colloquial FP, it power appearance item akin this:
\[\begin{aligned} \mathsf{q}(\mathsf{Var} \hspace{2pt} i) &= \mathsf{App} (\mathsf{Constr} \hspace{2pt} \texttt{"Var"}) (\mathsf{Num} \hspace{2pt} i)\\ \mathsf{q}(\mathsf{App} \hspace{2pt} e_1 \hspace{2pt} e_2) &= \mathsf{App}(\mathsf{App}(\mathsf{Constr} \hspace{2pt} \texttt{"App"}) (\mathsf{q} \hspace{2pt} e_1)) (\mathsf{q} \hspace{2pt} e_2)\\ \mathsf{q}(\mathsf{Lam} \hspace{2pt} e) &= \mathsf{App} (\mathsf{Constr} \hspace{2pt} \texttt{"Lam"}) (\mathsf{q} \hspace{2pt} e) \end{aligned}\]
Translated rear into our Church encoding:
\[\begin{aligned} \mathsf{q}(v \hspace{2pt} \underline{i}) &= a (v \hspace{2pt} \underline{2}) (\mathsf{qn} \hspace{2pt} \underline{i})\\ \mathsf{q}(a \hspace{2pt} e_1 \hspace{2pt} e_2) &= a (a (v \hspace{2pt} \underline{1}) (\mathsf{q} \hspace{2pt} e_1)) (\mathsf{q} \hspace{2pt} e_2)\\ \mathsf{q}(l \hspace{2pt} e) &= a (v \hspace{2pt} \underline{0}) (\mathsf{q} \hspace{2pt} e) \end{aligned}\]
where $\mathsf{qn}$ is a quasi-quoter for Church numerals (derived similarly). Note the correspondence between $v, a, l$ and $v \hspace{2pt} \underline{2}, v \hspace{2pt} \underline{1}, v \hspace{2pt} \underline{0}$ is resolute by our Church encoding gathering $\lambda v a l. \cdots$.
These three equations depict a fold complete the tree construction of the ASTs. Since Church encodings naturally grip folds, we can effortlessly rotate those equations into a sole term.
These constructions were carried out and justified concerning in Rocq, which you can see here.
The resulting Quine is shown below in de Bruijn notation:
((λ((λ0) (((λ(λ(λ(λ(λ((1 (((4 2) 1) 0)) (((3 2) 1) 0))))))) 0) ((λ(λ(λ(λ(0 (0 (0 (((((λ(λ(λ(λ(((3 ((((λ(λ(λ(λ((2 (3 (λ(λ(1 (1 0)))))) (((((λ(λ(λ(λ(1 (1 (((((λ(λ(λ(λ((0 (2 (3 (λ(λ(1 0)))))) (3 (λ(λ0)))))))) 3) 2) 1) 0))))))) 3) 2) 1) 0)))))) 2) 1) 0)) ((((λ(λ(λ(λ(2 ((2 (3 (λ(λ(1 0))))) 0)))))) 2) 1) 0)) ((((λ(λ(λ(1 (2 (λ(λ0))))))) 2) 1) 0)))))) 3) 2) 1) 0)))))))) 0)))) (λ(λ(λ(0 ((1 (0 (2 (λ(λ0))))) ((1 ((1 (0 (0 (0 (0 (0 ((1 ((1 (2 (λ(λ(1 0))))) ((1 ((1 ((1 (2 (λ(λ(1 (1 (1 (1 0)))))))) (2 (λ(λ(1 (1 0))))))) (2 (λ(λ(1 0)))))) (2 (λ(λ0)))))) ((1 ((1 ((1 (2 (λ(λ(1 (1 (1 0))))))) (2 (λ(λ(1 (1 0))))))) (2 (λ(λ(1 0)))))) (2 (λ(λ0))))))))))) (2 (λ(λ0))))) ((1 (0 (0 (0 (0 ((1 (2 (λ(λ0)))) ((1 (2 (λ(λ0)))) ((1 (2 (λ(λ0)))) ((1 ((1 ((1 ((1 (0 (0 (0 (0 ((1 ((1 ((1 (2 (λ(λ(1 (1 (1 0))))))) ((1 ((1 ((1 (0 (0 (0 (0 ((1 ((1 (2 (λ(λ(1 (1 0)))))) ((1 (2 (λ(λ(1 (1 (1 0))))))) (0 (0 ((1 (2 (λ(λ(1 0))))) ((1 (2 (λ(λ(1 0))))) (2 (λ(λ0)))))))))) ((1 ((1 ((1 ((1 (0 (0 (0 (0 ((1 (2 (λ(λ(1 0))))) ((1 (2 (λ(λ(1 0))))) ((1 ((1 ((1 ((1 (0 (0 (0 (0 ((1 ((1 (2 (λ(λ0)))) ((1 (2 (λ(λ(1 (1 0)))))) ((1 (2 (λ(λ(1 (1 (1 0))))))) (0 (0 ((1 (2 (λ(λ(1 0))))) (2 (λ(λ0)))))))))) ((1 (2 (λ(λ(1 (1 (1 0))))))) (0 (0 (2 (λ(λ0)))))))))))) (2 (λ(λ(1 (1 (1 0)))))))) (2 (λ(λ(1 (1 0))))))) (2 (λ(λ(1 0)))))) (2 (λ(λ0))))))))))) (2 (λ(λ(1 (1 (1 0)))))))) (2 (λ(λ(1 (1 0))))))) (2 (λ(λ(1 0)))))) (2 (λ(λ0)))))))))) (2 (λ(λ(1 (1 0))))))) (2 (λ(λ(1 0)))))) (2 (λ(λ0)))))) ((1 ((1 ((1 (0 (0 (0 (0 ((1 (2 (λ(λ(1 (1 0)))))) ((1 ((1 (2 (λ(λ(1 (1 0)))))) ((1 (2 (λ(λ(1 (1 (1 0))))))) (0 (0 ((1 (2 (λ(λ(1 0))))) (2 (λ(λ0))))))))) (2 (λ(λ0)))))))))) (2 (λ(λ(1 (1 0))))))) (2 (λ(λ(1 0)))))) (2 (λ(λ0)))))) ((1 ((1 ((1 (0 (0 (0 ((1 (2 (λ(λ(1 0))))) ((1 (2 (λ(λ(1 (1 0)))))) (0 (0 (2 (λ(λ0))))))))))) (2 (λ(λ(1 (1 0))))))) (2 (λ(λ(1 0)))))) (2 (λ(λ0)))))))))) (2 (λ(λ(1 (1 (1 0)))))))) (2 (λ(λ(1 (1 0))))))) (2 (λ(λ(1 0)))))) (2 (λ(λ0)))))))))))) (2 (λ(λ0)))))))))))
