|
Non-computable Julia sets
Author(s):
M.
Braverman;
M.
Yampolsky
Journal:
J. Amer. Math. Soc.
19
(2006),
551-578.
MSC (2000):
Primary 37F50;
Secondary 68Q17
Posted:
December 22, 2005
Retrieve article in:
PDF
Abstract |
References |
Similar articles |
Additional information
Abstract:
We show that under the definition of computability which is natural from the point of view of applications, there exist non-computable quadratic Julia sets.
References:
-
- [BCSS]
- L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation, Springer, New York, 1998. MR 1479636 (99a:68070)
- [ABC]
- A. Avila, X. Buff, A. Chéritat. Siegel disks with smooth boundaries. Acta Math. 193 (2004), no. 1, 1-30. MR 2155030
- [BBY1]
- I. Binder, M. Braverman, M. Yampolsky. Filled Julia sets with empty interior are computable, e-print math.DS/0410580 at Arxiv.org.
- [BBY2]
- I. Binder, M. Braverman, M. Yampolsky. On computational complexity of Siegel Julia sets, Commun. Math. Physics, to appear.
- [BB]
- E. Bishop, D.S. Bridges, Constructive Analysis. Springer-Verlag, Berlin, 1985. MR 0804042 (87d:03172)
- [Brv1]
- M. Braverman, Computational Complexity of Euclidean Sets: Hyperbolic Julia Sets are Poly-Time Computable, Proc. CCA 2004., Electr. Notes Theor. Comput. Sci. 120: 17-30 (2005).
- [Brv2]
- M. Braverman, Parabolic Julia sets are polynomial time computable. e-print math.DS/0505036 at Arxiv.org.
- [Bru]
- A.D. Brjuno. Analytic form of differential equations, Trans. Mosc. Math. Soc. 25(1971), 119-262. MR 0377192 (51:13365)
- [BC1]
- X. Buff, A. Chéritat, Quadratic Siegel disks with smooth boundaries. Preprint Univ. Paul Sabatier, Toulouse, III, Num. 242.
- [BC2]
- X. Buff, A. Chéritat, The Yoccoz function continuously estimates the size of Siegel disks, Annals of Math., to appear.
- [Do]
- A. Douady. Does a Julia set depend continuously on the polynomial? In Complex dynamical systems: The mathematics behind the Mandelbrot set and Julia sets. ed. R.L. Devaney, Proc. of Symposia in Applied Math., Vol. 49, Amer. Math. Soc., 1994, pp. 91-138. MR 1315535
- [DH1]
- A. Douady, J.H. Hubbard. Etude dynamique des polynômes complexes, I-II. Pub. Math. d'Orsay, 1984. MR 0762431 (87f:58072a), MR 0812271 (87f:58072b)
- [DH2]
- A. Douady, J.H. Hubbard. On the dynamics of polynomial-like mappings. Ann. Sci. École Norm. Sup., 18(1985), 287-343. MR 0816367 (87f:58083)
- [Grz]
- A. Grzegorczyk, Computable functionals, Fund. Math. 42, pp. 168-202, 1955. MR 0086756 (19:238b)
- [Ko1]
- K. Ko, Complexity Theory of Real Functions, Birkhäuser, Boston, 1991. MR 1137517 (93i:03057)
- [Ko2]
- K. Ko, Polynomial-time computability in analysis, in ``Handbook of Recursive Mathematics'', Volume 2 (1998), Recursive Algebra, Analysis and Combinatorics, Yu. L. Ershov et al. (Editors), pp. 1271-1317. MR 1673610 (2000e:03169)
- [Lac]
- D. Lacombe, Extension de la notion de fonction récursive aux fonctions d'une ou plusieurs variables réelles. I, C. R. Acad. Sci. Paris 240 (1955), 2478-2480; Extension de la notion de fonction récursive aux fonctions d'une ou plusieurs variables réelles. II, III, C. R. Acad. Sci. Paris 241 (1955), 13-14, 151-153. MR 0072079 (17:225d), MR 0072080 (17:225e)
- [Maz]
- S. Mazur, Computable analysis, Rosprawy Matematyczne, Warsaw, vol. 33 (1963). MR 0153553 (27:3517)
- [MMY]
- S. Marmi, P. Moussa, J.-C. Yoccoz, The Brjuno functions and their regularity properties, Commun. Math. Phys. 186(1997), 265-293.MR 1462766 (98e:58137)
- [Mat]
- Y. Matiyasevich, Hilbert's Tenth Problem, The MIT Press, Cambridge, London, 1993.MR 1244324 (94m:03002b)
- [McM1]
- C. McMullen. Complex dynamics and renormalization. Annals of Math. Studies, v.135, Princeton Univ. Press, 1994. MR 1312365 (96b:58097)
- [Mil]
- J. Milnor. Dynamics in one complex variable. Introductory lectures. Friedr. Vieweg & Sohn, Braunschweig, 1999. MR 1721240 (2002i:37057)
- [PZ]
- C. Petersen, S. Zakeri, On the Julia set of a typical quadratic polynomial with a Siegel disk. Ann. of Math. (2) 159(2004), no. 1, 1-52.MR 2051390 (2005c:37085)
- [Pom]
- C. Pommerenke, Boundary behaviour of conformal maps, Springer-Verlag, 1992.MR 1217706 (95b:30008)
- [Ret]
- R. Retinger. A fast algorithm for Julia sets of hyperbolic rational functions, Proc. of CCA 2004, Electr. Notes Theor. Comput. Sci. 120: 145-157 (2005).
- [RW]
- R. Rettinger, K. Weihrauch, The Computational Complexity of Some Julia Sets, in STOC'03, June 9-11, 2003, San Diego, California, USA. MR 2121048 (2005j:68060)
- [RZ]
- S. Rohde, M. Zinsmeister, Variation of the conformal radius, Journ. Anal. Math., 92(2004), pp. 105-115. MR 2072743 (2005g:30008)
- [Sie]
- C. Siegel, Iteration of analytic functions. Ann. of Math. (2) 43, (1942), 607-612.MR 0007044 (4:76c)
- [Sip]
- M. Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997.
- [Tur]
- A. M. Turing, On Computable Numbers, With an Application to the Entscheidungsproblem. In Proceedings, London Mathematical Society, 1936, pp. 230-265.
- [Wei]
- K. Weihrauch, Computable Analysis, Springer, Berlin, 2000.MR 1795407 (2002b:03129)
- [Yoc]
- J.-C. Yoccoz, Théorème de Siegel, nombres de Bruno et polynômes quadratiques, Petits diviseurs en dimension
 , S.M.F., Astérisque, 231(1995), 3-88. MR 1367353 (96m:58214)
Similar Articles:
Retrieve articles in Journal of the American Mathematical Society
with MSC
(2000):
37F50,
68Q17
Retrieve articles in all Journals with MSC
(2000):
37F50,
68Q17
Additional Information:
M.
Braverman
Affiliation:
Department of Computer Science, University of Toronto, Toronto, ON M5S 3G4, Canada
M.
Yampolsky
Affiliation:
Department of Mathematics, University of Toronto, Toronto, ON M5S 2E4, Canada
DOI:
10.1090/S0894-0347-05-00516-3
PII:
S 0894-0347(05)00516-3
Received by editor(s):
June 28, 2004
Posted:
December 22, 2005
Additional Notes:
The first author's research is supported by an NSERC CGS scholarship
The second author's research is supported by an NSERC operating grant
Copyright of article:
Copyright
2005,
American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.
|
Comments: webmaster@ams.org