Quines: Programs That Print Themselves

Introduction

Write a program that prints its own source code. The rules: no reading the file from disk, no peeking at a debugger. The program must compute its own text.

At first this seems circular. To print the program you must already contain the program, and the program that contains the program must contain the program that contains... The way out is an old logician's trick, the same one at the heart of Gödel's incompleteness theorems: split the program into a template and a quoted copy of that template. The code uses the quotation as data and prints it as code.

The name comes from philosopher W. V. O. Quine, who studied indirect self-reference. His paradox is the phrase: "yields falsehood when preceded by its quotation" yields falsehood when preceded by its quotation. The sentence does not mention itself; it builds itself by applying a rule to a quoted piece of text. Douglas Hofstadter named such self-printing programs quines in Gödel, Escher, Bach (1979).

The surprise is that this is not a clever hack of one language. Kleene's recursion theorem (1938) says self-reference is available in every acceptable model of computation, for any computable transformation of programs. That makes quines the friendliest corner of a theorem that proves the halting problem undecidable and also Rice's theorem.

The skeleton, in pseudocode:

t = "t = @; print(t with @ replaced by quote(t))"
print(t with @ replaced by quote(t))

The first line stores the template. The second line applies it to itself. The output is the two lines again.

Try It: Programs That Print Themselves

The demo has three parts. First, run a genuine quine and check that its output is identical to its source. Second, type any JavaScript you like: the builder wraps it so the resulting program performs your payload and then prints itself. Third, a toy model of a famous attack on trust in compilers.

<section>
  <h3>1. A program that prints itself</h3>
  <p class="hint">No input, no file access: the program below computes a string and prints it. Press Run and compare the output with the source, character by character.</p>
  <pre id="q1src" class="code"></pre>
  <div class="btns"><button id="q1run" type="button">Run</button></div>
  <div class="lbl">Output</div>
  <pre id="q1out" class="code out"></pre>
  <div class="status" id="q1status"></div>
</section>
<section>
  <h3>2. Build a quine around any payload</h3>
  <p class="hint">Type any JavaScript that calls print(). The builder wraps it in the self-printing skeleton, so the new program does its job and then prints its own source.</p>
  <div class="btns">
    <button id="p1" type="button" class="ghost">Print a message</button>
    <button id="p2" type="button" class="ghost">Count to 5</button>
    <button id="p3" type="button" class="ghost">Sum 1 to 10</button>
  </div>
  <label class="lbl" for="payload">Payload (JavaScript)</label>
  <textarea id="payload" rows="3" maxlength="300" spellcheck="false"></textarea>
  <div class="btns"><button id="build" type="button">Build and run</button></div>
  <div class="lbl">Generated program</div>
  <pre id="q2src" class="code"></pre>
  <div class="lbl">Printed lines (the last one is the program's own source)</div>
  <pre id="q2out" class="code out"></pre>
  <div class="status" id="q2status"></div>
</section>
<section>
  <h3>3. Trusting trust (toy model)</h3>
  <p class="hint">The sources below are clean. Plant the trojan once in the installed compiler, then rebuild everything from the clean sources and watch what survives.</p>
  <div class="cols">
    <div class="panel">
      <div class="lbl">Source code</div>
      <pre id="srcs" class="code"></pre>
      <div class="audit" id="audit"></div>
    </div>
    <div class="panel">
      <div class="lbl">Installed binaries</div>
      <pre id="bins" class="code"></pre>
    </div>
  </div>
  <div class="btns">
    <button id="s1" type="button">1. Plant trojan in the compiler binary</button>
    <button id="s2" type="button">2. Rebuild compiler from clean source</button>
    <button id="s3" type="button">3. Compile login</button>
    <button id="s4" type="button">4. Try the secret password</button>
    <button id="s0" type="button" class="ghost">Reset (trusted compiler)</button>
  </div>
  <div class="status" id="q3status">Everything is clean. Start with step 1, or compile login right away.</div>
  <p class="toy">Toy model: sources and binaries are plain strings and the compiler is a string substitution. Real attacks are far more intricate.</p>
</section>

:root { --bg: #ffffff; --fg: #1f2933; --muted: #52606d; --card: #f1f5f9; --line: #cbd5e1; --accent: #1d3557; --accent-fg: #ffffff; --ok: #0a7d33; --bad: #c92f3c; --code-bg: #eef2f7; }
@media (prefers-color-scheme: dark) {
  :root { --bg: #121821; --fg: #e4e9f0; --muted: #a3b1c2; --card: #1a2230; --line: #36445a; --accent: #9fb8e0; --accent-fg: #0d1520; --ok: #4cd37d; --bad: #ff7b86; --code-bg: #0e141d; }
}
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; background: var(--bg); color: var(--fg); margin: 0; padding: 14px 2px; }
section { border-bottom: 1px solid var(--line); padding: .6rem 0 1rem; }
h3 { font-size: 1.05rem; margin: .2rem 0 .4rem; }
.hint, .toy { font-size: .88rem; color: var(--muted); margin: 0 0 .6rem; line-height: 1.45; }
.toy { font-style: italic; margin-top: .6rem; }
.lbl { font-size: .8rem; font-weight: 700; text-transform: uppercase; letter-spacing: .04em; color: var(--muted); margin: .6rem 0 .25rem; display: block; }
pre.code { font: 12.5px/1.45 ui-monospace, Consolas, monospace; background: var(--code-bg); border: 1px solid var(--line); border-radius: 8px; padding: .55rem .65rem; margin: 0; white-space: pre-wrap; word-break: break-all; min-height: 2.2rem; }
pre.out { border-style: dashed; }
textarea { width: 100%; font: 13px/1.4 ui-monospace, Consolas, monospace; background: var(--code-bg); color: var(--fg); border: 1px solid var(--line); border-radius: 8px; padding: .5rem; resize: vertical; }
.btns { display: flex; gap: .45rem; flex-wrap: wrap; margin: .5rem 0; }
button { font: 600 13.5px system-ui, sans-serif; padding: .42rem .8rem; border: 1px solid var(--accent); background: var(--accent); color: var(--accent-fg); border-radius: 8px; cursor: pointer; }
button.ghost { background: transparent; color: var(--accent); }
.status { font-weight: 600; font-size: .95rem; margin: .5rem 0; min-height: 1.3em; }
.status.ok { color: var(--ok); }
.status.bad { color: var(--bad); }
.cols { display: grid; grid-template-columns: 1fr 1fr; gap: .6rem; }
@media (max-width: 520px) { .cols { grid-template-columns: 1fr; } }
.panel { min-width: 0; }
.audit { font-size: .82rem; margin-top: .3rem; color: var(--ok); font-weight: 600; }
.infected { color: var(--bad); font-weight: 700; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
const $ = (id) => document.getElementById(id);
const PLACE = '@';

function buildQuine(payload) {
  const body = (payload.trim() ? payload.trim() + '\n' : '') + 'print(t.replace("@", () => JSON.stringify(t)));';
  const tpl = 'const t = @;\n' + body;
  return tpl.replace(PLACE, () => JSON.stringify(tpl));
}

function runProgram(src) {
  const lines = [];
  const print = (x) => { lines.push(String(x)); };
  new Function('print', src)(print);
  return lines;
}

function setStatus(id, text, cls) {
  const el = $(id);
  el.textContent = text;
  el.className = 'status ' + (cls || '');
}

const QUINE = buildQuine('');
$('q1src').textContent = QUINE;

$('q1run').addEventListener('click', () => {
  try {
    const lines = runProgram(QUINE);
    const out = lines[lines.length - 1];
    $('q1out').textContent = out;
    if (out === QUINE) setStatus('q1status', fmt("Output equals source: a quine (%n% characters).", { n: out.length }), 'ok');
    else setStatus('q1status', "Output differs from the source.", 'bad');
  } catch (e) {
    setStatus('q1status', fmt("Error: %e%", { e: e.message }), 'bad');
  }
});

const PRESETS = {
  p1: 'print("Hello from a program that knows itself!");',
  p2: 'for (let i = 1; i <= 5; i++) print(i);',
  p3: 'let s = 0;\nfor (let i = 1; i <= 10; i++) s += i;\nprint("1 + ... + 10 = " + s);'
};
Object.keys(PRESETS).forEach((id) => {
  $(id).addEventListener('click', () => { $('payload').value = PRESETS[id]; build(); });
});

function build() {
  const payload = $('payload').value;
  const src = buildQuine(payload);
  $('q2src').textContent = src;
  try {
    const lines = runProgram(src);
    $('q2out').textContent = lines.join('\n----\n');
    const last = lines[lines.length - 1];
    if (last === src) setStatus('q2status', fmt("Verified: the last printed line equals the program (%n% characters), after %k% payload line(s).", { n: src.length, k: lines.length - 1 }), 'ok');
    else setStatus('q2status', "Output differs from the source.", 'bad');
  } catch (e) {
    $('q2out').textContent = '';
    setStatus('q2status', fmt("Error: %e%", { e: e.message }), 'bad');
  }
}
$('build').addEventListener('click', build);
$('payload').value = PRESETS.p2;
build();

const LOGIN_SRC = 'program: login\naccept(user, password) if check(user, password)';
const COMPILER_SRC = 'program: compiler\ncompile(source) = translate(source)';
const CLEAN = 'BIN<compiler>';
let installed = CLEAN;
let loginBin = null;

function nameOf(src) { return src.split('\n')[0].replace('program: ', ''); }

function compileWith(bin, src) {
  const name = nameOf(src);
  let out = 'BIN<' + name + '>';
  if (bin.indexOf('+trojan') !== -1) {
    if (name === 'login') out += ' +backdoor';
    if (name === 'compiler') out += ' +trojan';
  }
  return out;
}

function paint() {
  $('srcs').textContent = LOGIN_SRC + '\n\n' + COMPILER_SRC;
  const dirty = /trojan|backdoor/.test(LOGIN_SRC + COMPILER_SRC);
  $('audit').textContent = dirty ? '' : "Audit: no trojan in any source";
  const bins = $('bins');
  bins.innerHTML = '';
  const rows = [['compiler', installed], ['login', loginBin || "(not built yet)"]];
  rows.forEach(([label, text]) => {
    const div = document.createElement('div');
    div.textContent = label + ': ' + text;
    if (text.indexOf('+') !== -1) div.className = 'infected';
    bins.appendChild(div);
  });
}

$('s1').addEventListener('click', () => {
  installed = CLEAN + ' +trojan';
  paint();
  setStatus('q3status', "The compiler binary now carries the trojan. Its source is untouched.", '');
});
$('s2').addEventListener('click', () => {
  installed = compileWith(installed, COMPILER_SRC);
  paint();
  if (installed.indexOf('+trojan') !== -1) setStatus('q3status', "The rebuilt compiler is still infected: the old binary re-inserted the trojan while compiling the clean source.", 'bad');
  else setStatus('q3status', "The rebuilt compiler is clean: the compiler that built it was clean.", 'ok');
});
$('s3').addEventListener('click', () => {
  loginBin = compileWith(installed, LOGIN_SRC);
  paint();
  if (loginBin.indexOf('+backdoor') !== -1) setStatus('q3status', "login was compiled with a hidden backdoor that is not in its source.", 'bad');
  else setStatus('q3status', "login was compiled faithfully.", 'ok');
});
$('s4').addEventListener('click', () => {
  if (!loginBin) { setStatus('q3status', "Compile login first (step 3).", ''); return; }
  if (loginBin.indexOf('+backdoor') !== -1) setStatus('q3status', "Access granted with the secret password. Nothing in the sources explains it.", 'bad');
  else setStatus('q3status', "Access denied: only real credentials work.", 'ok');
});
$('s0').addEventListener('click', () => {
  installed = CLEAN;
  loginBin = null;
  paint();
  setStatus('q3status', "Everything is clean. Start with step 1, or compile login right away.", '');
});
paint();

<section>
  <h3>1. A program that prints itself</h3>
  <p class="hint">No input, no file access: the program below computes a string and prints it. Press Run and compare the output with the source, character by character.</p>
  <pre id="q1src" class="code"></pre>
  <div class="btns"><button id="q1run" type="button">Run</button></div>
  <div class="lbl">Output</div>
  <pre id="q1out" class="code out"></pre>
  <div class="status" id="q1status"></div>
</section>
<section>
  <h3>2. Build a quine around any payload</h3>
  <p class="hint">Type any JavaScript that calls print(). The builder wraps it in the self-printing skeleton, so the new program does its job and then prints its own source.</p>
  <div class="btns">
    <button id="p1" type="button" class="ghost">Print a message</button>
    <button id="p2" type="button" class="ghost">Count to 5</button>
    <button id="p3" type="button" class="ghost">Sum 1 to 10</button>
  </div>
  <label class="lbl" for="payload">Payload (JavaScript)</label>
  <textarea id="payload" rows="3" maxlength="300" spellcheck="false"></textarea>
  <div class="btns"><button id="build" type="button">Build and run</button></div>
  <div class="lbl">Generated program</div>
  <pre id="q2src" class="code"></pre>
  <div class="lbl">Printed lines (the last one is the program's own source)</div>
  <pre id="q2out" class="code out"></pre>
  <div class="status" id="q2status"></div>
</section>
<section>
  <h3>3. Trusting trust (toy model)</h3>
  <p class="hint">The sources below are clean. Plant the trojan once in the installed compiler, then rebuild everything from the clean sources and watch what survives.</p>
  <div class="cols">
    <div class="panel">
      <div class="lbl">Source code</div>
      <pre id="srcs" class="code"></pre>
      <div class="audit" id="audit"></div>
    </div>
    <div class="panel">
      <div class="lbl">Installed binaries</div>
      <pre id="bins" class="code"></pre>
    </div>
  </div>
  <div class="btns">
    <button id="s1" type="button">1. Plant trojan in the compiler binary</button>
    <button id="s2" type="button">2. Rebuild compiler from clean source</button>
    <button id="s3" type="button">3. Compile login</button>
    <button id="s4" type="button">4. Try the secret password</button>
    <button id="s0" type="button" class="ghost">Reset (trusted compiler)</button>
  </div>
  <div class="status" id="q3status">Everything is clean. Start with step 1, or compile login right away.</div>
  <p class="toy">Toy model: sources and binaries are plain strings and the compiler is a string substitution. Real attacks are far more intricate.</p>
</section>

:root { --bg: #ffffff; --fg: #1f2933; --muted: #52606d; --card: #f1f5f9; --line: #cbd5e1; --accent: #1d3557; --accent-fg: #ffffff; --ok: #0a7d33; --bad: #c92f3c; --code-bg: #eef2f7; }
@media (prefers-color-scheme: dark) {
  :root { --bg: #121821; --fg: #e4e9f0; --muted: #a3b1c2; --card: #1a2230; --line: #36445a; --accent: #9fb8e0; --accent-fg: #0d1520; --ok: #4cd37d; --bad: #ff7b86; --code-bg: #0e141d; }
}
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; background: var(--bg); color: var(--fg); margin: 0; padding: 14px 2px; }
section { border-bottom: 1px solid var(--line); padding: .6rem 0 1rem; }
h3 { font-size: 1.05rem; margin: .2rem 0 .4rem; }
.hint, .toy { font-size: .88rem; color: var(--muted); margin: 0 0 .6rem; line-height: 1.45; }
.toy { font-style: italic; margin-top: .6rem; }
.lbl { font-size: .8rem; font-weight: 700; text-transform: uppercase; letter-spacing: .04em; color: var(--muted); margin: .6rem 0 .25rem; display: block; }
pre.code { font: 12.5px/1.45 ui-monospace, Consolas, monospace; background: var(--code-bg); border: 1px solid var(--line); border-radius: 8px; padding: .55rem .65rem; margin: 0; white-space: pre-wrap; word-break: break-all; min-height: 2.2rem; }
pre.out { border-style: dashed; }
textarea { width: 100%; font: 13px/1.4 ui-monospace, Consolas, monospace; background: var(--code-bg); color: var(--fg); border: 1px solid var(--line); border-radius: 8px; padding: .5rem; resize: vertical; }
.btns { display: flex; gap: .45rem; flex-wrap: wrap; margin: .5rem 0; }
button { font: 600 13.5px system-ui, sans-serif; padding: .42rem .8rem; border: 1px solid var(--accent); background: var(--accent); color: var(--accent-fg); border-radius: 8px; cursor: pointer; }
button.ghost { background: transparent; color: var(--accent); }
.status { font-weight: 600; font-size: .95rem; margin: .5rem 0; min-height: 1.3em; }
.status.ok { color: var(--ok); }
.status.bad { color: var(--bad); }
.cols { display: grid; grid-template-columns: 1fr 1fr; gap: .6rem; }
@media (max-width: 520px) { .cols { grid-template-columns: 1fr; } }
.panel { min-width: 0; }
.audit { font-size: .82rem; margin-top: .3rem; color: var(--ok); font-weight: 600; }
.infected { color: var(--bad); font-weight: 700; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
const $ = (id) => document.getElementById(id);
const PLACE = '@';

function buildQuine(payload) {
  const body = (payload.trim() ? payload.trim() + '\n' : '') + 'print(t.replace("@", () => JSON.stringify(t)));';
  const tpl = 'const t = @;\n' + body;
  return tpl.replace(PLACE, () => JSON.stringify(tpl));
}

function runProgram(src) {
  const lines = [];
  const print = (x) => { lines.push(String(x)); };
  new Function('print', src)(print);
  return lines;
}

function setStatus(id, text, cls) {
  const el = $(id);
  el.textContent = text;
  el.className = 'status ' + (cls || '');
}

const QUINE = buildQuine('');
$('q1src').textContent = QUINE;

$('q1run').addEventListener('click', () => {
  try {
    const lines = runProgram(QUINE);
    const out = lines[lines.length - 1];
    $('q1out').textContent = out;
    if (out === QUINE) setStatus('q1status', fmt("Output equals source: a quine (%n% characters).", { n: out.length }), 'ok');
    else setStatus('q1status', "Output differs from the source.", 'bad');
  } catch (e) {
    setStatus('q1status', fmt("Error: %e%", { e: e.message }), 'bad');
  }
});

const PRESETS = {
  p1: 'print("Hello from a program that knows itself!");',
  p2: 'for (let i = 1; i <= 5; i++) print(i);',
  p3: 'let s = 0;\nfor (let i = 1; i <= 10; i++) s += i;\nprint("1 + ... + 10 = " + s);'
};
Object.keys(PRESETS).forEach((id) => {
  $(id).addEventListener('click', () => { $('payload').value = PRESETS[id]; build(); });
});

function build() {
  const payload = $('payload').value;
  const src = buildQuine(payload);
  $('q2src').textContent = src;
  try {
    const lines = runProgram(src);
    $('q2out').textContent = lines.join('\n----\n');
    const last = lines[lines.length - 1];
    if (last === src) setStatus('q2status', fmt("Verified: the last printed line equals the program (%n% characters), after %k% payload line(s).", { n: src.length, k: lines.length - 1 }), 'ok');
    else setStatus('q2status', "Output differs from the source.", 'bad');
  } catch (e) {
    $('q2out').textContent = '';
    setStatus('q2status', fmt("Error: %e%", { e: e.message }), 'bad');
  }
}
$('build').addEventListener('click', build);
$('payload').value = PRESETS.p2;
build();

const LOGIN_SRC = 'program: login\naccept(user, password) if check(user, password)';
const COMPILER_SRC = 'program: compiler\ncompile(source) = translate(source)';
const CLEAN = 'BIN<compiler>';
let installed = CLEAN;
let loginBin = null;

function nameOf(src) { return src.split('\n')[0].replace('program: ', ''); }

function compileWith(bin, src) {
  const name = nameOf(src);
  let out = 'BIN<' + name + '>';
  if (bin.indexOf('+trojan') !== -1) {
    if (name === 'login') out += ' +backdoor';
    if (name === 'compiler') out += ' +trojan';
  }
  return out;
}

function paint() {
  $('srcs').textContent = LOGIN_SRC + '\n\n' + COMPILER_SRC;
  const dirty = /trojan|backdoor/.test(LOGIN_SRC + COMPILER_SRC);
  $('audit').textContent = dirty ? '' : "Audit: no trojan in any source";
  const bins = $('bins');
  bins.innerHTML = '';
  const rows = [['compiler', installed], ['login', loginBin || "(not built yet)"]];
  rows.forEach(([label, text]) => {
    const div = document.createElement('div');
    div.textContent = label + ': ' + text;
    if (text.indexOf('+') !== -1) div.className = 'infected';
    bins.appendChild(div);
  });
}

$('s1').addEventListener('click', () => {
  installed = CLEAN + ' +trojan';
  paint();
  setStatus('q3status', "The compiler binary now carries the trojan. Its source is untouched.", '');
});
$('s2').addEventListener('click', () => {
  installed = compileWith(installed, COMPILER_SRC);
  paint();
  if (installed.indexOf('+trojan') !== -1) setStatus('q3status', "The rebuilt compiler is still infected: the old binary re-inserted the trojan while compiling the clean source.", 'bad');
  else setStatus('q3status', "The rebuilt compiler is clean: the compiler that built it was clean.", 'ok');
});
$('s3').addEventListener('click', () => {
  loginBin = compileWith(installed, LOGIN_SRC);
  paint();
  if (loginBin.indexOf('+backdoor') !== -1) setStatus('q3status', "login was compiled with a hidden backdoor that is not in its source.", 'bad');
  else setStatus('q3status', "login was compiled faithfully.", 'ok');
});
$('s4').addEventListener('click', () => {
  if (!loginBin) { setStatus('q3status', "Compile login first (step 3).", ''); return; }
  if (loginBin.indexOf('+backdoor') !== -1) setStatus('q3status', "Access granted with the secret password. Nothing in the sources explains it.", 'bad');
  else setStatus('q3status', "Access denied: only real credentials work.", 'ok');
});
$('s0').addEventListener('click', () => {
  installed = CLEAN;
  loginBin = null;
  paint();
  setStatus('q3status', "Everything is clean. Start with step 1, or compile login right away.", '');
});
paint();

Result

Console

Notice that the builder never reads the program text from anywhere. The program carries one copy as a quoted string (the data) and rebuilds the full text from that single copy (the code). That is exactly the recursion theorem's recipe, specialised to "print me".

The Real Complexity

Fix an acceptable numbering $\varphi_0, \varphi_1, \dots$ of the partial computable functions, where $\varphi_e$ is the function computed by program $e$ .

Kleene's second recursion theorem (1938). For every total computable function $f$ there is an index $e$ such that

\varphi_e = \varphi_{f(e)}.

Think of $f$ as any program transformer: add logging, negate the output, insert a delay. The theorem says some program behaves exactly the same after the transformation. A program $e$ is a fixed point up to behaviour.

Proof sketch. By the s-m-n theorem there is a total computable $g$ with

\varphi_{g(x)}(y) = \varphi_{f(\varphi_x(x))}(y).

In words: $g(x)$ is a program that first runs $x$ on its own index, then applies $f$ to the result, then runs that program on $y$ . Let $v$ be an index of $g$ and put $e = g(v)$ . Then $e$ is defined and

\varphi_e = \varphi_{g(v)} = \varphi_{f(\varphi_v(v))} = \varphi_{f(g(v))} = \varphi_{f(e)}.

The "program run on its own index" is the diagonal move of Cantor and Turing, applied to programs instead of sets.

Quines. Take $f(e)$ = a program that ignores its input and outputs the text of $e$ . The fixed point $e$ satisfies $\varphi_e = \varphi_{f(e)}$ , so $e$ outputs its own text. The quine in the demo is the same proof, unrolled.

Undecidability from the same tool.

Halting. Suppose a total program $H$ decides whether $\varphi_x(y)$ halts. Let $f(x)$ be the program that, on input $y$ , loops forever if $H$ says $\varphi_x(y)$ halts, and halts otherwise. A fixed point $e$ halts on $y$ exactly when $f(e)$ halts on $y$ , which happens exactly when $e$ does not halt on $y$ . Contradiction, so $H$ cannot exist.
Rice's theorem. Let $P$ be a nontrivial property of the function computed (some programs have it, some do not). Pick $a$ with property $P$ and $b$ without. If $P$ were decidable, let $f(x) = b$ when $x \in P$ and $f(x) = a$ otherwise. A fixed point $e$ has $\varphi_e = \varphi_{f(e)}$ , so $e$ and $f(e)$ have the same property, but $f$ was built to flip it. Contradiction.

Costs.

Quantity	Bound
Building the quine skeleton around a payload of length $n$	$O(n)$ time
Length of the result in the demo's construction	$2n + O(1)$ (the payload appears once as data, once as code)
Number of quines in a language	infinite (every payload gives a new one)

The constant depends on the language, never on the payload. That is the quantitative content of the theorem: self-reference is cheap.

Relatives. Gödel's diagonal lemma is the same construction inside arithmetic: for every formula $\psi(x)$ there is a sentence $\sigma$ with $\vdash \sigma \leftrightarrow \psi(\ulcorner\sigma\urcorner)$ , which yields incompleteness. Kleene's version replaces provability by computation, which links directly to lambda calculus fixed-point combinators and the Church–Turing thesis.

Where It Matters

Self-reference shows up wherever a system must describe or build itself.

Self-reproducing machines. In the 1940s John von Neumann asked what a machine needs in order to copy itself without infinite regress. His answer, worked out as a cellular automaton and published posthumously in 1966, is a constructor that builds from a description, plus a copier that duplicates the description. A quine is the software version: the quoted template is the description, the code that unquotes it is the constructor. The same two-part logic, a description plus machinery that reads and copies it, was later recognised in DNA replication. See also cellular automata.
Trusting trust. In his Turing Award lecture, "Reflections on Trusting Trust" (published in 1984), Ken Thompson described a compiler modified to do two things: insert a backdoor when compiling the login program, and re-insert both modifications when compiling the compiler itself. Once the infected binary exists, the malicious code can be removed from the compiler's source and it still survives every rebuild. The mechanism needs a quine-like step so that the compiler can reproduce its own modification. The countermeasure published by David A. Wheeler, diverse double-compiling, compares builds from independent compilers.
Quine relays. A quine may pass the baton to a different language, which passes it on, until the last program prints the first. Yusuke Endoh's Quine Relay chains 128 programming languages. Ouroboros programs close such a loop.
Descriptions of descriptions. In Kolmogorov complexity a program is the shortest description of its own output. A quine is the extreme case where the description and the described object are the same text.
Proofs of impossibility. The same fixed-point argument underlies the undecidability results in the halting problem and Rice's theorem.

Conclusion

A quine looks like a magic trick and is a theorem. Split a program into a template and a quoted copy of the template, and it can reproduce its text without ever reading it. Kleene's recursion theorem generalises the trick: for every computable way of rewriting programs, some program is unchanged in behaviour.

That one fact builds quines, proves the halting problem undecidable, proves Rice's theorem, and explains why you cannot fully trust a binary by reading source code alone. Self-reference is not the enemy of computation. It is one of its central tools, and it comes with its own limits, which are the subject of Gödel's incompleteness theorems.

Comments

Loading comments...

https://www.kipuhub.com/en/article/quines-recursion-theorem/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Quines and Kleene's Recursion Theorem

How a program can know its own source