The Halting Problem states, loosely, that there is no algorithm that can 
take an arbitrary computer program and decide [in finite time] whether 
that program will run forever or come to a half after a finite time.

The HP does *not* say that it's impossible to tell whether a program 
halts. It is quite possible to tell that certain programs do in fact 
halt. And it is also quite possible to tell that others are never going 
to halt. The HP says that it is impossible to tell FOR EVERY POSSIBLE 
PROGRAM. Big difference.

To illustrate, consider the following program:

Let A = 0.2499
Let B = 0.01
Let X = 0
Let Y = 0
While (X*X + Y*Y < 4.0)
{
   T = X*X - Y*Y + A
   Y = 2*X*Y + B
   X = T
}
Halt

Does this halt? Or does it run forever?

You know what? If you change the first two lines, you change how long 
the program runs for. For some choices of A and B, the program stops 
instantly. For others, it runs for hours or even days and then stops. 
And for yet others, it runs provably FOREVER.

You might think that some simple mathematical structure describes the 
set of points for which the program does or doesn't stop. You might even 
try to graph this set of points to try to work out its structure. 
Fortunately, you needn't bother. Somebody has already done it for you:

http://tinyurl.com/2ca4o9

Think you can decide whether an arbitrary point on the screen is black 
or white in finite time? If you do, I imagine there are people who would 
be seriously interested to hear from you... ;-)

For each point on the screen, there is essentially a program - the 
program that determines the level set to which that point belongs. To 
repeat what I said above: for many points, it is *easy* to determine 
whether the program will halt. The HP doesn't say otherwise. What it 
says is that you cannot tell for *every* point. And, indeed, looking at 
the image, you can quickly see that whether you run the program directly 
or try to do some tricky geometric stuff, with a boundary this 
complicated, it's going to take a hell of a long time in some cases. 
And, by extension, some cases will unavoidably take an infinite amount 
of time...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message