Undecidability Proofs

Mathematical Logic · Axiom Academy

Step-by-step walkthroughs of four fundamental undecidability proofs in computability theory Excellent work! You've completed all four undecidability proofs. Here's what we learned: The Halting Problem: The fundamental undecidable problem, proven by diagonalization. No algorithm can determine whether an arbitrary program halts on a given input. Reduction Technique: To prove a problem undecidable, reduce a known undecidable problem to it. If the new problem were decidable, the known undecidable problem would also be decidable (contradiction). A_TM Undecidability: The acceptance problem for Turing machines is undecidable. This is proven by reducing the Halting Problem to A_TM. EMPTY_TM Undecidability: Determining if a Turing machine accepts any strings is undecidable. This is proven by reducing A_TM to EMPTY_TM using a clever construction. Rice's Theorem: A powerful meta-theorem stating that any non-trivial semantic property of Turing machines is undecidable. This allows us to prove undecidability without explicit reductions. Proof Strategies: Diagonalization for direct proofs (Halting Problem), reduction for relative undecidability (A_TM, EMPTY_TM), and Rice's Theorem for property-based problems. These proof techniques are fundamental to computability theory and demonstrate the inherent limits of computation. Understanding these methods will help you prove undecidability for many other problems!

This is the written version of the interactive lesson above. See the full Mathematical Logic course.