On 08/10/2010 00:39, Tomek Sowiński wrote:
<snip>
What's the halting problem?
Basically, it's the challenge of determining algorithmically whether an
arbitrary algorithm given arbitrary input will eventually halt or carry
on running forever.
The point is that the halting problem is known to be unsolvable. The
standard proof of this is as follows. Suppose the halt analyser
algorithm we seek exists. Call it WillHalt(Algorithm, Input). Then we
can consider WillHalt(Algorithm, Algorithm).
Then we can define a new algorithm, LoopIfHaltsOnItself(Algorithm),
defined as
if WillHalt(Algorithm, Algorithm) then
loop forever
else
return
Now try to analyse the outcome of LoopIfHaltsOnItself(LoopIfHaltsOnItself).
Personally, I think it's a shame that the halting problem can't be
solved. If it could, we could use it to solve many mathematical
problems that have as it happens remained unsolved for centuries.
Stewart.
