Quine · a program that prints itself

A quine is a program that, when executed, prints its own source code. No file I/O, no introspection — the program builds its own source from its own behaviour. Quines exist in every Turing-complete language, and constructing one is the simplest, cleanest demonstration of Kleene's recursion theorem (Sipser §6.1).

A quine is the case t(⟨R⟩, w) = ⟨R⟩ — the function simply outputs its own description. The construction works in any language with string manipulation. Once you can write a quine, the rest of the recursion theorem follows from the same data/code-split trick.

The asymmetry is what makes it work. The string S describes what the program will do; the printer code P actually does it. P reads S as data, prints S as data (escaped), then prints the unescaped instructions encoded in S. Because S describes P's own behaviour exactly, the output reassembles to the original source.

Same trick, three syntaxes:

Python:
s='s=%r;print(s%%s)';print(s%s)

JavaScript:
(function f(){console.log('('+f+')()');})()

Lisp:
((lambda (x) (list x (list (quote quote) x)))
 (quote (lambda (x) (list x (list (quote quote) x)))))

The Python version is the most readable: the string s contains a format-template that says "the string variable s, then printf-formatted with itself." When you execute it, the placeholder %r gets replaced by repr(s), which is s itself with quotes around it. The output reproduces the source.

• No file I/O. A quine doesn't read its own source from disk — that would be trivial. The program only operates on internal string variables. The match between source and output is forced by the construction, not by introspection.
• The string encoding is the hard part. Getting quotes, backslashes, and escapes right is the practical difficulty. Most quine bugs are escape bugs, not logic bugs.
• The recursion theorem ≠ recursion. Recursion (a function calling itself by name) is unrelated to the recursion theorem (a program obtaining its own description). The name collision is historical and unfortunate.
• A quine is a constructive proof, not just an example. The recursion theorem says a program with property X exists for any computable X — but the quine construction shows you how to build it. That constructive power is what makes the theorem useful for proofs.

• Q1. Isn't this cheating — reading its own source file?
  No file I/O is allowed or needed. The program only operates on the string variable S, which happens to encode (a description of) the source. The match between source and output is forced by the construction: the printer reassembles its source from the data stored in S.
• Q2. How does this relate to the recursion theorem?
  The recursion theorem says any TM can effectively access its own description ⟨R⟩. The quine is the simplest case: the TM uses that self-access to print ⟨R⟩ itself. More general uses replace "print ⟨R⟩" with arbitrary computable t(⟨R⟩, w).
• Q3. Why is the recursion theorem useful for proving undecidability?
  It lets a hypothetical TM M reason about its own description without diagonalisation gymnastics. Rice's theorem (Problem 14), for example, builds an M that does the opposite of whatever a candidate decider D claims about ⟨M⟩. The recursion theorem makes that construction routine — no need to think about indices and codes.
• Q4. What's the simplest quine you know?
  Python one-liner: s='s=%r;print(s%%s)';print(s%s). Sixteen characters of payload, eighteen of housekeeping. The %r formatter quotes s automatically; %% escapes a literal % in the format string.
• Q5. Are there languages where quines are impossible?
  Yes — languages without string-manipulation primitives (e.g., pure forms of Brainfuck with no output buffering) can fail. The recursion theorem holds for Turing-complete languages but requires self-printable code as a primitive — and not every Turing-complete language is self-printable in a small program.

Sipser: §6.1, Theorem 6.3 (recursion theorem) and Theorem 6.5 (corollary: every TM "knows" its own description). Lecture notes: Module 3 slide 5 walks through the T = A·B construction underlying the recursion theorem. Companion problems: P14 (Rice's theorem), P15 (fixed-point version), P16 (self-aware TM).