Halting problem (was: "in" everywhere)

[Stewart Gordon]

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.