Reducibility and Advanced Computability Theory

Corresponds to Sipser, Chapters 5–6. Rather than re-deriving undecidability from scratch each time (via diagonalization), reducibility transfers a known undecidable problem’s hardness to a new problem: if solving the new problem would let you solve the known-undecidable one, the new problem is undecidable too — made rigorous as mapping reducibility ($A \le_m B$: a computable function translating instances of $A$ into equivalent instances of $B$), with reductions via computation histories (encoding “does this Turing machine ever reach this state” as an instance of a language-theoretic problem) as the main proof technique. The advanced-topics half covers the recursion theorem (a Turing machine can be built to obtain its own description and act on it — the rigorous version of “self-reference,” underlying viruses and Gödel’s incompleteness theorem alike), decidability results for certain logical theories (and undecidability for others), Turing reducibility (allowing a machine oracle access to another language, strictly more general than mapping reducibility), and Kolmogorov complexity as a definition of the information content of a single string — see kolmogorov-complexity for the full treatment, which this note defers to rather than duplicates.

Outline (TODO — flesh out each)

• Undecidable problems from language theory
• Reductions via computation histories
• A simple undecidable problem
• Mapping reducibility — computable functions, formal definition
• The recursion theorem — self-reference, applications
• Decidability of logical theories
• Turing reducibility
• A definition of information (pointer to kolmogorov-complexity)