Invisible wrote:

> the halting problem talks about ANY POSSIBLE 
> PROGRAM. You could write something really freakin' bizare, and there's 
> no hope of an algorithm puzzling it out.

I think the Mandelbrot set is interesting here. You can write a program 
that computes how many iterations it takes for a specific orbit to 
escape. The set of inputs for which this program does not halt is 
precisely the Mandelbrot set - and as we all know, the boundary of this 
set is ludicrously complex. You can try to parameterise it in various 
ways. You can just run the iteration, you can try to make use of the 
repeating geometry, but no matter which way you look at it, any possible 
algorithm is going to take an infinite number of steps *somewhere* along 
the boundary. It's an inescapable and obvious fact that you simply can't 
determine whether *every* point is inside or outside the Mandelbrot set 
in a finite number of steps.

I find that a useful way to think about the Halting Problem. It shows 
that the program in question doesn't even need to be complicated...

Post a reply to this message