Sunday, December 27, 2009

The Standard Halting Problem Proof has a Major Flaw

The halting problem: the problem of figuring out whether or not a program will halt (not run forever) based on a description of the program, its machine and the input.

The standard proof that this is not solvable boils down to the following:

Imagine you had a program that could solve this problem. You could easily modify it to, instead of saying "this program will halt", run forever if the in put program would have halted. You could run the program on itself. The result is that the program will halt if it doesn't halt and not halt if it halts: a contradiction. Therefore such a program cannot be made.

Simple and clever right? Well what if you wanted to know if a program would output "red" or "blue". This really can be accomplished very simply. No question about that. Well, what if you write a wrapper that outputs red if the input program would have output blue and blue if the input program would have output red. Now feed this program to itself. You get the same contradiction.

Thus the logical flaw in the standard halting problem proof is exposed. There isn't something special about a program that doesn't halt. It's a false logical trick.

It's sort of like using a compiler to compile itself.

No comments:

Post a Comment