The recursion theorem · fixed-point form

This is the cleaner, more powerful statement of the recursion theorem. Sipser's classic Theorem 6.3 (every TM can obtain its own description) is a special case. Quines (Problem 13) are another special case: t outputs a program-that-prints-its-argument, and the fixed point is a program-that-prints-itself.

The two non-obvious moves: q is the constructive engine — it converts an arbitrary program description ⟨P⟩ into a self-aware version ⟨P'⟩ that has its own code as data. The s-m-n theorem (or just direct construction) guarantees q is computable. The second move is plugging ⟨t∘q⟩ back into q to get R. That self-application is the closing of the loop.

Let t : Σ* → Σ* take ⟨M⟩ and return the description of the TM obtained by swapping q_accept and q_reject in M. Clearly L(t(⟨M⟩)) = Σ* \ L(M) for halting M.

The recursion theorem gives R with L(R) = L(t(⟨R⟩)) = Σ* \ L(R). So L(R) is its own complement — possible only if L(R) is undefined on some inputs (R loops). The fixed point exists, and exploring why it must loop is a nice consequence: no halting TM can be its own complement under accept/reject swap.

• Fixed point is semantic, not syntactic. R and t(⟨R⟩) might be completely different programs — different states, different tape alphabets. They just recognise the same language.
• t must be total. If t loops on some ⟨P⟩, the construction breaks because we can't form ⟨t∘q⟩ reliably. Most natural transformations are total: rename states, add transitions, swap accept/reject.
• The recursion theorem doesn't say R is unique. Many fixed points may exist for a given t. The theorem only guarantees existence.
• You don't need to know s-m-n by heart. The s-m-n theorem just says "you can build a program that hard-codes some of its inputs as constants" — every programming language has this trivially. The proof's structure is the lesson, not the s-m-n syntax.

• Q1. Why is the fixed-point form stronger than the quine?
  Quine is t = identity. Fixed-point works for any computable t — including "rewrite every accept into a reject" or "double the number of states".
• Q2. Why is t required to be total?
  If t loops on some input, the fixed-point construction can fail. Totality ensures t(⟨P⟩) is always defined.
• Q3. Sketch the proof.
  Use the s-m-n theorem to define a computable q that maps any ⟨P⟩ to ⟨P'⟩ = a program that on input x first writes ⟨P'⟩ on its tape, then runs P(⟨P'⟩, x). Apply q to t to get R = q(t).
• Q4. Concrete example.
  Let t replace every accept state with reject. There exists a TM R such that L(R) equals the language of R-with-accept-and-reject-swapped — meaning L(R) is its own complement. Since L(R) = Σ* \ L(R) is impossible for halting TMs, this R must loop on some inputs. The recursion theorem still produces it.
• Q5. Where does this get used to prove undecidability?
  Rice's theorem (Problem 14) uses it to dodge diagonalisation. If P were a decider for any non-trivial language property, the fixed-point theorem produces a machine that contradicts P's classification of itself. Cleaner than building the diagonal machine D by hand.

Sipser: §6.1, Theorem 6.8 (fixed-point form) and Theorem 6.9 (corollaries). Lecture notes: Module 3 slide 5 has the T = A·B construction. Companion problems: P13 (quine, special case), P14 (Rice via recursion theorem), P16 (self-aware TM).