On 05 Nov 2011, at 17:22, Jason Resch wrote:



On Fri, Nov 4, 2011 at 10:35 AM, Bruno Marchal <marc...@ulb.ac.be> wrote:

- the Mandelbrot set + zooms (I suspect)
etc.



Bruno,

This idea intrigued me. Could you provide some elaboration on how zooms of the Mandelbrot set could be universal?

I am talking of the rational Mandelbrot set. I conjecture that the universal question "x belongs to W_y" can be reduced to the question a/ b + c/d i belongs to the rational Mandelbrot set, with a, b, c, d being integers. (W_y = the domain of the yth partial computable function phi_y)

This wouldn't be as astonishing than reducing "x belongs to W_y" to the question "are x and y solutions to some degree 4 polynomial diophantine equation (and the possibility of this follows from Matiyazevitch theorem).

If a rational complex number belongs to the M set, by zooming long enough on it, you will know if it is the case, but if it does not belong, it might be that you will never know it. In the case of the notion of computability "on a ring" (like R or C) Blum, Shub and Smale(*) have solved that conjecture positively, but this cannot be used to make the rational M set universal. I think that it is still an open problem.

Technically, I have a beginning of a proof based on the idea that the Mandelbrot set (well, its complementary) can be seen as the set of z such that z does not belong to its Julia set, making the Mandelbrot set diagonalizing on the Julia sets. Unlike Julia sets it inherits some closure property, which makes me finding such idea (the universality of the M set) rather plausible.

That would be nice, because it would make the M set a compact view of UD* (a complete execution of a universal dovetailer). Each little Mandelbrot sets are surrounded by infinite bifurcation processes which have the little M set as limit, that can illustrate the complexity of the comp measure problem, because such a limit is "geometrically" infinitely complex, yet algorithmically very simple (as the code for the M set is very short).

Note that Penrose has made a similar conjecture.

(*) http://www.amazon.com/Complexity-Real-Computation-Lenore-Blum/dp/0387982817

Bruno

http://iridia.ulb.ac.be/~marchal/



--
You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to 
everything-list+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/everything-list?hl=en.

Reply via email to