The Halting Problem

Mathematical Logic · Axiom Academy

Discover one of the most profound results in computer science: a problem that no computer program can ever solve, no matter how clever the algorithm. In other words, we want to know: can we write a program that takes any other program as input and determines whether that program will eventually stop or run forever? Input: A Turing machine M and input string w Output: YES (if it halts) or NO (if it runs forever) This is a profound negative result. It tells us that there are fundamental limits to computation—some problems cannot be solved by any algorithm, no matter how clever or how much time and space we provide. 3. Proof by Diagonalization: The Setup We'll prove this by contradiction . The proof uses a clever technique called diagonalization , similar to Cantor's diagonal argument for uncountable sets. Assume there exists a halting problem solver H Use H to construct a new machine D Show that D leads to a logical contradiction Conclude that our assumption was false— H cannot exist Let's assume, for the sake of contradiction, that a Turing machine H exists that solves the halting problem. This means: 4. Constructing the Diagonalizer D Now we'll construct a new Turing machine D using our hypothetical halting solver H . Machine D takes a Turing machine M as input and does the following: Notice the key property: D does the opposite of what H predicts. If H says a machine halts, D loops forever. If H says it loops forever, D halts. 5. The Contradiction: What Happens with D(D)?

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