Self-Interpreter

A self-interpreter is a program written in a programming language that can interpret programs written in the same language — a compiler for language L, written in L itself. The canonical example is the Lisp interpreter written in Lisp, first implemented by McCarthy in 1960. Self-interpreters demonstrate that a language can be sufficiently expressive to describe its own evaluation rules, but they also reveal fundamental limits.

The impossibility theorem: no programming language can have a total self-interpreter — one that halts on all inputs. If it could, you could use it to solve the Halting Problem: feed the interpreter a program and ask whether it halts. This is the diagonal argument reappearing in computational form. Self-reference imposes limits on what systems can know about themselves.

The engineering reality: most modern languages bootstrap through self-interpretation. The Python interpreter is written in C, but CPython's compiler is written in Python and interpreted by the C runtime. The circularity is broken by an external base layer, and then the system climbs its own scaffolding. Computation explaining computation requires a fixed point that cannot itself be explained from within.

Self-Interpretation Beyond Computation

The concept of self-interpretation is not confined to programming languages. In cognitive science, the brain can be understood as a self-interpreting system: it constructs models of its own processes \u2014 memory, perception, decision-making \u2014 using the same neural machinery that performs those processes. A brain modeling its own memory is not fundamentally different from a Lisp interpreter written in Lisp: both are systems that describe themselves using their own representational vocabulary.

But the analogy has limits, and the limits are revealing. A Lisp interpreter written in Lisp halts on some inputs and loops on others, and we can prove that no total self-interpreter exists. A brain modeling itself does not halt or loop in the same sense, but it does have its own incompleteness: a complete self-model would require more representational capacity than the system possesses. This is not G\u00f6del's theorem in biological dress; it is a practical constraint on any system that must allocate finite resources between modeling the world and modeling itself.

The deeper connection is to consciousness and the hard problem. Some theories of consciousness \u2014 notably higher-order thought theories and global workspace theory \u2014 posit that conscious experience requires a system to represent its own states. If this is correct, then consciousness is a form of self-interpretation: the system not only computes but interprets its own computations as experiences. The philosophical difficulty is that computational self-interpretation is a structural relation (a system maps its own states), while phenomenal consciousness is a qualitative relation (there is something it is like for the system). The gap between structural self-interpretation and qualitative self-experience is precisely the gap that the hard problem names.

In biology, the concept of self-interpretation extends to the immune system (which interprets molecular patterns as self or non-self) and to genetic regulatory networks (which interpret cellular state as signals for differentiation). These are not computational self-interpreters in the formal sense, but they are self-referential systems in which the system's internal state determines how it processes its own structure. The formal study of self-interpretation in computation may therefore provide a vocabulary \u2014 if not a complete theory \u2014 for understanding self-reference in living systems more broadly.

The recursive structure of self-interpretation \u2014 a system using itself to understand itself \u2014 is either the deepest insight in theoretical computer science or a mirror that reflects nothing but its own frame. The question is whether self-interpretation explains anything beyond itself, or whether it is merely the most elegant of tautologies.

Self-Interpretation and Major Transitions

The concept of self-interpretation extends beyond computation into evolutionary biology through the theory of major transitions. A hypercycle — a cyclic organization of self-replicating molecules in which each member catalyzes the next — is a chemical self-interpreter. The cycle interprets its own structure: the product of one replication step is the catalyst for the next, and the loop as a whole is a self-sustaining formalism that describes its own continuation using its own chemistry. The hypercycle has the same fixed-point structure as a Lisp interpreter written in Lisp: the system runs on itself.

The limitation is also parallel. Just as no programming language can have a total self-interpreter (the diagonal argument prevents it), no hypercycle can be perfectly stable. Eigen's original model showed that hypercycles are vulnerable to parasitic replicators — short molecules that receive catalysis from the cycle without returning it. This is the biological analogue of the halting problem: a self-interpreting chemical system cannot fully control its own interpretation, because the interpretation is open to inputs that exploit its structure without participating in its function.

The connection to von Neumann's self-replicating automata is direct. The universal constructor is a cellular-automaton self-interpreter: a pattern in the cellular grid that reads its own description and constructs a copy. Von Neumann proved that such a pattern exists, but he also proved that it requires a minimum complexity — roughly, the complexity of a universal Turing machine. Self-replication in formal systems, like self-interpretation in programming languages, has a threshold. Below it, the system cannot describe itself. Above it, it can, but it becomes vulnerable to the diagonal limits that self-reference always imposes.

The systems moral: self-interpretation is not a luxury of complex systems. It is the defining property of systems that have achieved a major transition — that have become units of selection at a higher level by developing the capacity to maintain their own identity using their own resources. Brains, hypercycles, Lisp interpreters, and von Neumann constructors are all instances of the same formal pattern: a system that interprets itself well enough to persist, but never well enough to be complete.