Self-aware Turing machines

The recursion theorem (Sipser §6.1) says: any TM can effectively obtain its own description ⟨M⟩ on its tape and use it as data. This unlocks a remarkably short proof that A_TM is undecidable — one with no explicit diagonal argument visible.

The diagonalisation is hidden inside M itself, not stretched across a separate machine D' as in Problem 3. The recursion theorem absorbs the bookkeeping; what remains is just "build a program that defies its own classifier."

The proofs are the same proof in different clothes. The diagonal argument shows up somewhere — the recursion theorem just packages it. The recursion-theorem version is easier to generalise: Rice's theorem (Problem 14) uses the same template, replacing "D decides A_TM" with "D decides any non-trivial property of L(M)."

Spell out one execution. Suppose D is your candidate decider for A_TM. By the recursion theorem, there exists a TM M that on any input w:

1. Writes down ⟨M⟩ (its own code).
2. Calls D on the pair ⟨M, w⟩, gets some yes/no answer.
3. If D says "M accepts w," then M rejects w.
4. If D says "M does not accept w," then M accepts w.

Pick any w. D produces some classification. M does the opposite. So D's classification is wrong on (⟨M⟩, w). One wrong classification is enough — D was supposed to be correct on every input. Contradiction.

• "Obtain ⟨M⟩" is not magic. The recursion theorem says ⟨M⟩ is constructible — there's an actual procedure (Problem 13's quine machinery). It's not hand-waving; it's a buildable feature of the TM.
• M is not the same as D's classification of M. M produces an answer (accept/reject w). D produces a classification ("M accepts w" or not). The contradiction is that M's answer disagrees with D's classification on (M, w). Don't conflate the two.
• This proof generalises; the Problem 3 proof doesn't easily. Try repeating Problem 3's argument for "the language of M is empty." It gets awkward. The recursion-theorem proof reads "build M to do the opposite of what D says about M's language" and just works. That's the value.
• The recursion theorem does not bootstrap the universe. It only says: given any computable t, you can build a fixed point of t. It does not let you compute uncomputable functions.

• Q1. Compare with the Problem 3 proof.
  Problem 3 builds an external machine D' that flips D, and asks what happens on D' fed itself. Problem 16's M flips D from inside itself, using the recursion theorem to get ⟨M⟩ for free. Same contradiction, but the recursion theorem absorbs the awkward "build D'" step. The technique generalises immediately to Rice's theorem.
• Q2. Does M actually "know" its own code?
  In the sense the recursion theorem provides: yes. ⟨M⟩ is constructible by M itself, using the quine technique from Problem 13. It's not a runtime introspection feature — it's baked into M's construction at compile time.
• Q3. Where else is self-reference used in this course?
  Rice's theorem (P14) is the next natural application. Gödel's incompleteness theorems use the same trick at the level of formal proofs. The fixed-point combinator Y in λ-calculus is the functional analog. In complexity theory, complete problems via "diagonalisation against polynomial-time TMs" use the same kind of self-reference.
• Q4. Does this work for HALT_TM too?
  Yes. Replace D's role: assume D' decides HALT_TM. Build M with access to ⟨M⟩: on input w, ask D'(⟨M, w⟩); if D' says "halts," loop; if D' says "doesn't halt," halt. M's behaviour contradicts D's classification.
• Q5. Can we use this to prove A_DFA undecidable?
  No — A_DFA is decidable. The recursion theorem requires the language being defined to have an actual fixed point in the model, which works for TMs. DFAs don't have unrestricted self-reference because they can't encode arbitrary programs.

Sipser: Theorem 6.5 (recursion theorem corollary — A_TM proof). Lecture notes: Module 3 slide 5 (T = A·B construction). Companion problems: P3 (classic A_TM proof, contrast), P13 (quine, prerequisite), P14 (Rice via recursion theorem), P15 (fixed-point form).