Outline of the Proof that the Halting Problem is Unsolvable

Suppose we have a solution S to the Halting Problem:

In what follows, we include S into a larger program and then analyze how that larger program works.

• The only speculative step will be getting S
• All subsequent steps utilize simple programming, although details depend upon the program language utilized behind the scenes.

Step 1: Adjust Inputs

Although the Halting Problem treats P and I as separate, we observe that both P and I are characters (or files). Thus, we could consider giving S the same characters as both P and I.

• If P represents nonsense as input to P, the program may crash.
• However, when a program crashes, it halts.
• From the perspective of the Halting Problem, a crash is perfectly acceptable, and the result for the Problem should be "Halts".

Add a step, so that the input will be a program, and that input is also fed to the program. The resulting expanded solution S' will determine whether or not any program P halts when given itself as input.

Step 2: Adjust Output

We add a stage at the end of processing to get a new program S", based on the output of Solution S.

• If S outputs "Halts", then new program S" will go into an infinite loop.
• If S outputs "Does not Halt", S" prints "Done" and halts

Putting these pieces together, we obtain an expanded program with S at its core.

Summary:

Given a solutions S of the Halting Problem, we have constructed a new program S".

• S" takes programs as input
• For any program P, S" feeds P to solution S both as program and input
• S produces an output
• S" adds a step at the end, based on the output of S

What happens when S" is given itself as input?

We base our analysis on our Solution S to the Halting Problem:

• S indicates that either S" halts when given S" as input or S" does not halt.
• If S indicates S" halts
  • S" goes into an infinite loop, so
  • S" does not halt, and
  • S gave the wrong answer
• If S indicates S" does not halt
  • S" prints "Done" and halts, and
  • S gave the wrong answer
• Altogether, S gives the wrong answer when analyzing whether S" halts when given S" as input.

Conclusion: Program S contains an error; S does not always produce a correct result for the Halting Problem, so S does not actually solve that problem.

Since this result follows for any claimed solution of the Halting Problem, we conclude there are no solutions to the Halting Problem;
The Halting Problem is Unsolvable

created: 3 January 2007 last revised: 7 January 2007

previous  next