|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |