Chapter 6 · Advanced Computability

The recursion theorem

Can a program use its own source code? The recursion theorem says yes — any machine can obtain its own description and compute with it, with no paradox.

Definition · Recursion theorem

For any computable t(x, y) there is a machine R that, on input w, computes t(⟨R⟩, w) — that is, R has access to its own description ⟨R⟩.

This legitimizes self-reference as a programming technique. It gives a one-line proof that Aᴛᴍ is undecidable, and it is the reason quines (programs that print themselves) must exist.

No magic
Obtaining your own description is a computable operation — the theorem simply guarantees the fixed point always exists.