Is the Mandelbrot Set undecidable?

[Calcyman]

There are many simple systems that are undecidable, and are equivalent to the Halting Problem. Of course, one of the first systems shown to be undecidable was the Universal Turing Machine, where determining whether it halts on a given input cannot be accomplished by a computer. Equivalently, there are some statements in mathematics, which are true, yet cannot be proved true (Gödel's incompleteness theorem).

A more interesting problem is the 3-body problem. This is a system of three particles under Newtonian gravity, and is also an undecidable problem. There is no computer such that, when provided with the eighteen initial real numbers, can determine the eventual fate of the system.

My question is: does the Mandelbrot Set exhibit a similar property? In other words, is there a point on the complex plane for every Turing Machine, such that determining whether it lies inside the Mandelbrot Set is equivalent to determining whether that Turing machine halts?

If so, that would possibly be the simplest universal system. If not, we can still define a different fractal with this property, and it would be more intricate than the Mandelbrot Set!

[Schlega]

There's not a point for every Turing machine, but there is a Turing machine for every point, which halts if the point iterates outside the bailout radius.

If there is a natural way of parametrizing all possible Turing machines, it would be interesting to see what the resulting fractal looks like. I suspect it would look more like a Cantor dust than a Mandelbrot set though.

[fractower]

If we ignore for a moment the real (infinite precision, not ) number representation problem, one can easily prove that there are an infinite number of infinite length orbits. Except for a few special points, all points on the boundary of the set have an infinite length orbit. Now consider two points very near the boundary where one is inside the set and one is outside. Both points will follow very closely the orbit of the boundary point except the one outside the set will ultimately diverge (reach a bailout diameter). If you have enough time you can calculate 10^100 iterations and still not know if 10^101 will see a divergence. I suspect I read this somewhere but it seems points sufficiently close to the boundary are undecidable.

This also implies that finding the boundary is not possible except where analytic solutions exist.

[David Makin]

I believe Fractover is correct - in fact about the majority of escape-time fractals, for instance the same essentially applies to the standard Newton except in that case the issue is complicated by the fact that the exact boundary points between the attractors are such that the Newton formula breaks down and such points form a special Set of therir own i.e. a distinct boundary Set (or Sets) dividing the Sets for the usual attractors.

[Calcyman]

Rephrasing this a different way, is there a general analytic solution for determining whether a point lies in the set (applicable to all points), or is the best way to simply iterate the point to see whether it diverges?

...but there is a Turing machine for every point, which halts if the point iterates outside the bailout radius.

Every computable point. There is not, for example, a Turing machine corresponding to C + 0i, where C is Chaitin's constant.

If there is a natural way of parametrizing all possible Turing machines, it would be interesting to see what the resulting fractal looks like.

Very difficult to plot on a computer, that's for certain! I've mentioned that the 18-dimensional fractal corresponding to the 3-body problem is a 'universal fractal' (where there is a point corresponding to each Turing machine), but it would be nice to have a universal two-dimensional fractal. Certain Collatz-like systems can be universal (according to John Conway), and the Collatz conjecture can be made into a rather aesthetic fractal, by generalising it to the complex numbers. Hence, with a universal Collatz-like system, one can construct a universal fractal.

[cKleinhuis]

ehrm, people,  if space is infinite, and that is the usual case on turing machines, the problem could be reduced
in my eyes to find an loop in the iteration process, at the point where a previous point is touched, the function can savely
return that the point belongs to the set, so, with enough memory for storing previous positions it would be ( a very time consuming ) a decidable process ... correct me if i am wrong ....

[David Makin]

Trifox, I think you may be correct for most points on well-behaved fractals but any fractal that contains strange attractors or orbits that are simply infinitely random would present a problem
Also of course the fact is that for some points such a periodicity would be infinite and so such points would not be decideable - of course infinite period is exactly equivalent to an orbit that is simply infinitely random !

[fractower]

Even finite period orbits are somewhat difficult to detect because in most cases the iterations are only asymptotically approaching the orbit.

[cKleinhuis]

my point would be that in a computer memory, with limited float precision ( no matter what you set it to )
one would also have to deal with rounding errors ( all the time ) but how would a fractal with unlimited strange
attractors would look like ??!?!?


asymptotic approach should lead to one certain starting point, or not ? no matter how it would behave,
the period is detectable .... period detecting is quite demanding, because one would have to include ALL
previous iterations steps, this would lead to a Exponential O Notation, which is not even polynomial
and thus ( WARNING: just a thought of me, nothing to prove, nothin proved !! WARNING!)

but anyhow the algorithm is implemented, deciding if a point lies inside/outside is at least a NP Hard Problem
http://en.wikipedia.org/wiki/P_versus_NP_problem

so, in my eyes the answer to the originial thread theme would be:

yes it is decidable ... because of the orbit period detection and bailout methods for both outcomes ...

wasnt the question if the mandelbrot is decidable ?

and in my eyes, for the mandelbrot this holds true, regarding the fact that period detection is possible,
no matter how many strange attractors would be there

the problem with float precision is just a matter of space, and not time, so with enough space ( and the turing band is inifinite by definition )
it could be done, although calculating with big numbers can be demanding, but ( correct me if i am wrong ) isnt that just
a O(N)/O)(ln n )/O(n ln n )  problem ?

[trafassel]

The book "The Emperor's New Mind" by Roger Penrose (1989) contains some discussion on the undecidability of the Mandelbrot set. The interesting result is declared in a footnote - "Leonore Blum have found, that the inverse of the Mandelbrot Set is not recursive".

... and here is the proof, that the the Mandelbrot Set undecidable:

http://books.google.de/books?id=zxtrVqUP-AwC&pg=PA55&lpg=PA55&dq=Leonore+Blum+Mandelbrot&source=bl&ots=m-9m9KCdjK&sig=54cfQnPwyqmU_j1fh9KLTGGBG0w&hl=de&ei=btV6TJvME4PKswam-OWyDQ&sa=X&oi=book_result&ct=result&resnum=1&ved=0CBYQ6AEwAA#v=onepage&q&f=false

[cKleinhuis]

oh,  i better should take a closer look at this, sorry for not knowin ;

 

[fractower]

I think the question has bifurcated as fractals often do.

The Mandelbrot set is not calculable.

The approximation of the Mandelbrot set using finite precision floating point  representations is calculable. Assume the halting conditions are bailout or orbit repeat, then any orbit that does not bailout must eventually repeat because there are only a finite number of numbers representable.

This discussion reminded me of a nice repeat detection algorithm I saw some where.

Number the iteration results starting with [tex]R_0[\tex]. Remember and compare against only the last result whose index was a power of 2. If the starting point is already in an orbit of period N then you are guaranteed to detect the orbit in 2N iterations. If the orbit is entered at some later iteration then the detection will be the next higher power of 2 + N iterations.

[Calcyman]

... and here is the proof, that the the Mandelbrot Set undecidable:

Many thanks -- that was exactly what I was looking for!