Proof by Contradiction Setup
You'll learn how to set up the classic proof that shows the halting problem cannot be solved by any algorithm.
Now that we understand what the halting problem is and why it matters, we need to prove it's actually undecidable. We'll use a powerful technique called proof by contradiction, where we assume the opposite of what we want to prove and show this leads to an impossible situation.
The Assumption
Here's how we set up the contradiction:
Assume there exists a Turing machine H that solves the halting problem. This hypothetical machine H takes two inputs:
- A description of any Turing machine
M - An input string
w
And H always decides correctly:
Haccepts ifMhalts on inputwHrejects ifMruns forever on inputw
Why This Setup?
If such an H existed, we could solve the halting problem—every program could be checked for infinite loops before running. But we're going to show this assumption leads to a logical impossibility.
Think of it like assuming you can build a "perfect lie detector." If we can construct a scenario where the detector gives contradictory answers to the same question, we've proven no such detector can exist.
Next Steps
Once we assume H exists, we'll construct a new machine based on H that creates a paradox: it halts if and only if it doesn't halt. This logical impossibility proves our assumption was wrong—H cannot exist.
Key Takeaway: The proof by contradiction begins by assuming a halting-problem solver H exists; we'll then construct a paradox that shows this assumption is impossible, proving the halting problem is undecidable.