Invisible <voi### [at] devnull> wrote:
> If there was a Magic() subroutine that could take the object code to 
> your whole program and tell you whether it halts or not, then you could 
> write a BlackMagic() subroutine that calls Magic(BlackMagic()) and then 
> purposely does the opposite of whatever Magic() claims that it's going 
> to do. Hence, it is impossible for Magic() to yield the correct answer, 
> since BlackMagic() will do the opposite of whatever Magic() claims it 
> will do.

  That's just the simplest proof. It doesn't mean it's the only one, or
that the only way of making an undecidable algorithm is by making it call
the halting problem solver itself.

  While this is not a proof of anything, it's however, a marvelously simple
example of why solving the halting problem is extremely difficult:

  "A program that goes through all even numbers and checks if one of them
is a counter-example to the Goldbach's conjecture. The program terminates
when it finds the first such number."

  An algorithm which solves the halting problem would prove (or disprove)
the Goldbach's conjecture with its answer (if the answer is "it never
halts", then it proves the conjecture, while the answer "it halts"
disproves it, and this disproval would be valid even if it couldn't give
the counter-example).

  How could an algorithm resolve whether that program will ever halt or not?
Top mathematicians have struggled with that problem for over 250 years, to
no avail. A program which solves the halting problem for any given program
would make proving basically *all* mathematical problems trivial.

  While, as said, this is not a proof that it's not possible, it gives a good
idea why it would be a tremendously difficult problem to solve.

-- 
                                                          - Warp

Post a reply to this message