Problem Detail: The Mandelbrot set is a beautiful creature in Mathematics. There are a lot of beautiful images of this set created with high precision, so obviously this set is “computable” in some sense. However, what concerns me is the fact that it is not even recursively enumerable – simply because the set is uncountable. This could be resolved by requiring some sort of finite representation of the points. Furthermore, although we know for sure that a lot of points belong to the set and others do not, there are also a lot of points whose membership in the set we don’t know. All the images we’ve seen so far may include a lot of points that “up to n iterations kept in bound,” but those points may not actually belong to the set. So, for a given point with a finite presentation, the problem “Does this point belong to the set?” has not been proved to be decidable yet, if I am right. Now, in what sense (by which definition) can we say the Mandelbrot set is “computable”?
Asked By : Earth Engine
Answered By : Yuval Filmus
There are several ways of defining what it means for the Mandelbrot set to be computable. One possible definition is the Blum–Shub–Smale model. In this model, real computation is modelled by a machine similar to a RAM machine, whose access to real numbers is restricted to basic arithmetic and comparisons. Blum and Smale showed that the Mandelbrot set is uncomputable in this model, though its complement can be recursively enumerated using the traditional algorithm used for drawing them. Another model is computable analysis, in which the Mandelbrot set is probably computable, as shown by Hertling (conditional on a widely believed conjecture, the hyperbolicity conjecture). In this model, computing the Mandelbrot set means being able to compute an approximation to the Mandelbrot set, within any desired accuracy (for the exact definition, see the reference on computable analysis). Why is it, then, that the computer seems to be able to draw the Mandelbrot set? The main difficulty in showing that the traditional algorithm works is that it is difficult to tell in advance how many iterations to run before we decide that the point belongs to the set. Hertling shows that if the widely believed hyperbolicity conjecture holds, then there is a reasonable such bound. Presumably, the programs simply wait long enough; or they don’t wait long enough, but only get a small fraction of the points wrong.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/42685
