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.