The program that prints itself

Four earlier essays have run the same argument and reached the same kind of conclusion. The row that is not on the list showed that no list of infinite sequences contains them all. The list that cannot contain itself turned the argument on sets, the sentence that says it has no proof on provability, and the word that cannot describe itself on naming. Each time the diagonal produced something that could not exist, and the conclusion was a limit.

That last essay ended by pointing out that the diagonal can be run the other way. Instead of flipping the diagonal to produce an object that differs from every row, use it to produce an object that agrees with its own row — a fixed point. In the setting of programs this reversal has a name, Kleene’s recursion theorem, and a concrete, runnable consequence: there are programs whose output is their own text.

Why it looks impossible #

The difficulty in writing a program that prints itself is easy to feel. A program that prints some text must contain that text, or instructions for making it. So a program that prints its own text must contain its own text — and then, being larger than that text by at least the instructions that print it, cannot be it.

The naive attempt runs into this at once. A program print("X") prints X. To make it print itself, X would have to be print("X"), so the program would be print("print(\"X\")"), which prints something else; and every attempt to repair the inside pushes the problem one level further in. It is the regress of a map that contains a map of itself, and it looks like a proof that no program can do it. Indeed the same reasoning, correctly applied, does prove something: a program cannot contain its own text as a literal string, since the string would have to be a proper part of itself. What the reasoning misses is that containing and producing are different, and that a short program can produce a long text.

The regress is broken by the same trick that broke it in every earlier diagonal argument: do not include the text; include a description, and a rule that applies the description to itself.

Taking the program apart #

The program in the opening figure is (f=>f(f))(f=>"(f=>f(f))("+f+")"), and it has two parts. The first, (f=>f(f)), is a machine: given a function $f$, it calls $f$ with $f$ itself as the argument. The second is the function it is given, which takes its argument — itself — and builds a piece of text: the characters (f=>f(f))(, followed by its own program text, followed by ). In JavaScript, a function used in a place where text is expected turns into its own program text, and that is the one resource the construction needs: some way for a description to be turned into the text of that description.

Put together: the machine hands the description to itself; the description writes out the machine’s text and then its own; the result is exactly the whole program. There is no regress, because the program never contains its own text — it contains a description and a way of applying it, and the text is produced by the application. The whole program is thirty-two characters, and a program that did something more with its text afterwards would be longer only by the length of that something; the self-reference costs a fixed, small overhead, not an infinite one.

This is the diagonal. Think of a table whose rows are descriptions and whose columns are descriptions too, with the entry in row $d$, column $e$ being “what $d$ builds when given $e$”. The machine picks out the diagonal entry — $d$ applied to $d$ — and the program is the point on the diagonal where what a description builds is the description’s own program.

The theorem, and what it promises #

Kleene’s recursion theorem, from 1938, is the general statement. Take any computable way $F$ of transforming programs — any procedure that takes a program’s text and produces another program’s text. Then there is a program $e$ that behaves exactly like $F(e)$: whatever $F(e)$ computes, $e$ computes too.

The program that prints itself is the case where $F$ turns any program into “print this program’s text”. The fixed point $e$ behaves like “print $e$’s text” — so $e$ prints itself. And nothing about the construction depends on printing. Replace the final step by any computation on the rebuilt text, and the result is a program that computes that thing about itself.

The practical meaning of the theorem is that a program may always be assumed to have access to its own text. Any algorithm that could be written with its own description as an extra input can be written without it; the recursion theorem supplies the description. That sounds like a curiosity and is a tool. It is how one proves that no program can decide, for every program, whether it halts — a program that has its own text can ask the supposed decider about itself and do the opposite — and it is the engine of the essay that follows this one, where it proves that no property of what a program does can be decided.

The same trick settles a question the word that cannot describe itself left in words. Berry’s paradox asked for “the smallest number not nameable in fewer than twenty words”; its computational form is Gregory Chaitin’s theorem that no program can prove any particular string needs a description much longer than the program itself. The proof is a program that, knowing its own text and therefore its own length, searches for a proof that some string needs a longer description than that, and prints the first such string it finds — describing it, by its own existence, more briefly than the proof claimed possible. So the search never succeeds. The recursion theorem supplies the knowledge of its own length, and the paradox becomes a theorem about the limits of proof.

The halting problem in two lines #

With the theorem in hand, the most famous impossibility in computing takes two lines. Suppose some program $H$ decided, for every program and input, whether that program halts on that input. Write a program $e$ that obtains its own text — the recursion theorem says it can — asks $H$ whether $e$ halts, and then does the opposite: loops for ever if $H$ says it halts, and halts at once if $H$ says it does not. Whatever $H$ answers about $e$ is wrong. So there is no such $H$.

The earlier proof, in the row that is not on the list, built the troublesome program by flipping the diagonal of a table of programs and inputs. This one builds it by using the diagonal unflipped to give a program its own text, and then flipping its behaviour. The two proofs are the same argument arranged differently, and the recursion theorem is the reason the second arrangement is available: it packages the diagonal once, so that every later impossibility proof can simply say “let the program consult the decider about itself”.

The same packaging works in logic. Necessity that means provable described the logic of what a formal system can prove about its own proofs, and the key fact behind it, Löb’s theorem, is proved by constructing a sentence stating that its own provability implies some other sentence — a fixed point of exactly this kind, built by the arithmetic version of the recursion theorem. The diagonal lemma of logic and the recursion theorem of computation are one construction in two languages.

One theorem behind both directions #

Why should the same move produce impossibilities in one setting and constructions in another? William Lawvere gave the answer in 1969, and the first of these essays quoted it: whenever every function from a set to itself can be represented by a row of some table, every function from that set to itself has a fixed point. Read one way, a function with no fixed point — flipping a bit, negating a sentence — shows that not every function can be represented, which is Cantor’s theorem and its relatives. Read the other way, in a setting where every function can be represented — the computable transformations of programs, each of which is itself a program — every function has a fixed point, which is Kleene’s theorem.

So the refutations and the construction are the contrapositive of each other. Cantor could not list the sequences because flipping has no fixed point; Kleene can find a self-printing program because programs can represent every computable transformation of programs, including the one that turns any program into “print this”. The diagonal does the same work in both; what changes is whether the world it acts on is rich enough to contain its own transformations.

The same construction in a sentence #

The construction does not need a computer. W. V. Quine found it in English, and the name quine for a self-printing program, given by Douglas Hofstadter, honours him.

The sentence has exactly the program’s anatomy. “Print two copies of the following, the second in quotation marks:” is the machine, which applies a description to itself — quoting is the English way of turning a phrase into a description of that phrase. The quoted copy is the description. And the output is the whole.

Quine used the same shape for a darker purpose. His sentence

“yields falsehood when preceded by its quotation” yields falsehood when preceded by its quotation

says of itself that it is false. It is the liar paradox, built from quotation and nothing else — no word like “this”, no pointing — and it shows that the self-reference behind the sentence that says it has no proof is not a trick of formal systems but something any language able to quote and concatenate can do. Gödel’s construction is this sentence with “yields falsehood” replaced by “has no proof”, and with arithmetic doing the quoting.

Set side by side, the two tables show that the difference between a paradox and a program is one step. Grelling’s table flips its diagonal and asks whether the result is a row — and since it cannot be, the adjective heterological has no consistent answer about itself. The program takes its diagonal unflipped and makes the result a row: what the description builds from itself is, by construction, a program in the list. The earlier refutations said that some object cannot exist; the recursion theorem says that for programs, the fixed point always does.

A program that prints its successor #

Self-reproduction with a change is the natural next step, and it was studied before there were computers to run it.

John von Neumann, in lectures around 1948, asked what a machine would need in order to build a copy of itself, and answered with the same division the program shows. It needs a description of itself, a constructor that builds whatever a description describes, and a copier that duplicates the description and hands the copy to the offspring. Crucially, the description is used twice in two different ways — once read, to build the body, and once copied, uninterpreted, into the child — and that double use is exactly what breaks the regress.

Five years later the structure of DNA was found, and it works the same way: the genome is read to build the cell’s proteins, and copied, as text, into the daughter cell. Von Neumann had described the logical architecture of biological reproduction before its chemistry was known, by thinking about the recursion theorem’s problem. A counter that changes from generation to generation, as in the figure, is a mutation, and a lineage of such programs is evolution without selection.

Programs that know too much about themselves #

The same power has uses nobody wanted. A computer virus is a program that copies its own text into other programs, and it needs nothing more than the recursion theorem guarantees. Fred Cohen, who first studied computer viruses formally in 1984, used exactly the diagonal argument to prove that no program can detect every virus: a supposed detector could be consulted by a program with access to its own text, which then does the opposite of what the detector predicts.

Ken Thompson showed the same year, in a lecture called Reflections on Trusting Trust, how a compiler can be made to recognise when it is compiling itself and insert a hidden change into the result — so that the change survives even after it has been removed from the compiler’s source text, because the compiled compiler reproduces it. Every step of his construction is a quine with a payload. The lesson he drew was that no amount of reading a program’s text establishes what a program will do, which is the informal version of the theorem in the next essay. Both results turn on the same ability. A program that can obtain its own text can compare it with anything, copy it anywhere, and reason about what a checker would say of it — and a checker that has to be right about every such program is defeated by the one that consults it about itself.

What the programs cannot show #

The figures run particular programs in one language and check their output. They show that self-reproducing programs exist in JavaScript; they do not show the theorem, which says one exists for every computable transformation in every reasonable programming language. That generality comes from the construction — the machine-plus-description pattern works whenever a language can turn a program into its own text and run one program on another — and it is the construction, not the examples, that is the proof.

The programs also lean on one convenience that makes them short: JavaScript turns a function into its own text on request. In a language without that, the description has to carry its own text explicitly as a string, and the quoting of quotation marks inside quotation marks makes self-printing programs longer and much harder to read, though never impossible. And no figure can show the fixed point for a transformation that is not about text at all — a program that behaves like its own compiled version, say — though the theorem guarantees one exists. Nor do the figures say anything about efficiency: the recursion theorem guarantees a fixed point and says nothing about how long it takes to run, and some of the fixed points it produces are enormously slower than the programs they imitate.

Still open: the smallest self-reproducers #

The recursion theorem is a closed result and so is its consequence that self-printing programs exist in every language powerful enough to compute. What is not closed is quantitative: how short can a self-reproducing program be in a given language, and what is the simplest system in which self-reproduction occurs at all?

For programming languages the shortest quines are found by search and ingenuity, not by theory. For physical and chemical systems the question is the origin of life’s: von Neumann’s architecture needs a constructor able to build anything its description describes, which is enormously complex, and in cellular automata his original design ran to tens of thousands of cells, while patterns that copy themselves without a universal constructor — Christopher Langton’s loops of 1984 among them — need fewer than a hundred, with no known lower bound for either. What the minimal apparatus for reproduction is — in a cellular automaton, in chemistry, or in principle — is an open question, and the recursion theorem says only that, once computation is available, self-reproduction comes free. Between those two facts — that the logic of self-reproduction is simple, and that its physical implementation has never been built from scratch with a known minimum of parts — lies one of the oldest open problems at the border of mathematics and biology.