Claim: The Halting Problem is unsolvable.

Note: The claim says not only that no one has found a solution yet, but also that no one can find a solution in the future either.

• This is not a matter of cleverness.
• Solutions do not, and cannot, exist

How to show something cannot exist?

Approach:

We show that if anyone claims to have a solution S to the Halting Problem, then S fails to give the right answer in at least one case.

• Since any claimed solution S is wrong, there can be no solution;
• This makes the Halting Problem unsolvable.

created 3 January 2007 last revised 7 January 2007

previous  next