Computability versus Topological Properties of Julia Sets

Part of the Algorithms and Computation in Mathematics book series (AACIM, volume 23)

To provide some intuition why the filled Julia set is computable even when the Julia set is not, we propose a “toy” example. As a first step, let us denote byW(θ,w) the closed wedge in the unit disc U around direction θ with width w at the base, which penetrates the disc to depth 1/2 (as shown in Figure 6.1(a)).


Turing Machine Topological Model Riemann Mapping Continue Fraction Expansion Topological Disk 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. ABC04.
    A. Avila, X. Buff, and A. Chéritat, Siegel disks with smooth boundaries, Acta Math. 193 (2004), no. 1, 1–30.zbMATHCrossRefMathSciNetGoogle Scholar
  2. Ahl06.
    L. Ahlfors, Lectures on Quasiconformal Mappings, American Mathematical Society, 2006.Google Scholar
  3. Bak75.
    A. Baker, Transcendental Number Theory, Cambridge University Press, 1975.Google Scholar
  4. BB85.
    E. Bishop and D. S. Bridges, Constructive Analysis, Springer-Verlag, Berlin, 1985.zbMATHGoogle Scholar
  5. BBCO.
    A. Blokh, X. Buff, A. Chéritat, and L. Oversteegen, The solar Julia sets of basic Cre-mer quadratic polynomials, Available from Scholar
  6. BBY06.
    I. Binder, M. Braverman, and M. Yampolsky, On computational complexity of Siegel Julia sets, Commun. Math. Phys. 264 (2006), no. 2, 317–334.CrossRefMathSciNetGoogle Scholar
  7. BBY07a.
    ——, Filled Julia sets with empty interior are computable, Journ. of FoCM, 7 (2007), 405–416.zbMATHMathSciNetGoogle Scholar
  8. BBY07b.
    ——, On computational complexity ofRiemann Mapping, Arkiv for Matematik, 45 (2007), 221–239.zbMATHCrossRefMathSciNetGoogle Scholar
  9. BC02.
    X. Buff and A. Chéritat, Quadratic Siegel disks with smooth boundaries, Tech. Report 242, Univ. Toulouse, 2002.Google Scholar
  10. BC05.
    ——, Ensembles de Julia quadratiques de mesure de Lebesgue strictementpositive, Comptes Rendus Math. (2005), no. 341/11, 669–674.Google Scholar
  11. BC06a.
    M. Braverman and S. Cook, Computing over the reals: Foundations for scientific computing, Notices of the AMS 53 (2006), no. 3, 318–329.zbMATHMathSciNetGoogle Scholar
  12. BC06b.
    X. Buff and A. Chéritat, The Brjuno function continuously estimates the size of quadratic Siegel disks, Annals of Math. 164 (2006), no. 1, 265–312.zbMATHGoogle Scholar
  13. BCSS98.
    L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and real computation, Springer-Verlag, New York, 1998.Google Scholar
  14. BM37.
    S. Banach and S. Mazur, Sur les fonctions caluclables, Ann. Polon. Math. 16 (1937).Google Scholar
  15. Bra04.
    M. Braverman, Computational complexity of Euclidean sets: Hyperbolic Julia sets are poly-time computable, Master's thesis, University of Toronto, 2004.Google Scholar
  16. Bra05.
    ——, On the complexity of real functions., Proceedings of 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23–25 October 2005, Pittsburgh, PA, USA, 2005, pp. 155–164.Google Scholar
  17. Bra06.
    ——, Parabolic Julia sets are polynomial time computable, Nonlinearity 19 (2006), no. 6, 1383–1401.zbMATHCrossRefMathSciNetGoogle Scholar
  18. Brj71.
    A. D. Brjuno, Analytic forms of differential equations, Trans. Mosc. Math. Soc 25 (1971).Google Scholar
  19. BW99.
    V. Brattka and K. Weihrauch, Computability of subsets of Euclidean space I: Closed and compact subsets, Theoretical Computer Science 219 (1999), 65–93.zbMATHCrossRefMathSciNetGoogle Scholar
  20. BY06.
    M. Braverman and M. Yampolsky, Non-computable Julia sets, Journ. Amer. Math. Soc. 19 (2006), no. 3, 551–578.zbMATHCrossRefMathSciNetGoogle Scholar
  21. CK95.
    A. Chou and K. Ko, Computational complexity of two-dimensional regions, SIAM J. Comput. 24 (1995), 923–947.zbMATHCrossRefMathSciNetGoogle Scholar
  22. Coo06.
    S Cook, P versus NPproblem, The Millenium Prize Problems (J Carlson, A Jaffe, and A Wiles, eds.), Clay Math. Inst. and Amer. Math. Soc, 2006, pp. 87–104.Google Scholar
  23. Dav88.
    G. David, Solutions de l'équation de Beltrami avec ǁμǁ∞= 1, Ann. Acad. Sci. Fenn. Ser. AI Math. 13 (1988), 25–70.zbMATHGoogle Scholar
  24. Dev04.
    R. Devaney, Cantor and Sierpinski, Julia and Fatou: Complex topology meets complex dynamics, Notices of the AMS 51 (2004), no. 1, 9–15.zbMATHMathSciNetGoogle Scholar
  25. dFdM99.
    E. de Faria and W. de Melo, Rigidity of critical circle mappings I, J. Eur. Math. Soc. (JEMS) 1 (1999), no. 4, 339–392.zbMATHCrossRefMathSciNetGoogle Scholar
  26. DH85.
    A. Douady and Hubbard J. H., On the dynamics of polynomial-like mappings, Ann. scient. Ec. Norm. Sup., 4e série 18 (1985), 287–343.MathSciNetGoogle Scholar
  27. Dou88.
    A. Douady, Disques de Siegel et anneaux de Herman. Seminaire Bourbaki, Vol. 1986/87, Astérisque 152–153 (1988), no. 4, 151–172.MathSciNetGoogle Scholar
  28. Dou93.
    ——, Descriptions of compact sets in c, Topological methods in modern mathematics (Stony Brook, NY, 1991) (1993), 429–465.Google Scholar
  29. Dou94.
    ——, Does a Julia set depend continuously on the polynomial?, Complex dynamical systems: The mathematics behind the Mandelbrot set and Julia sets (R L De-vaney, ed.), Proc. of Symposia in Applied Math., vol. 49, Amer. Math. Soc, 1994, pp. 91–138.Google Scholar
  30. Fis89.
    Y. Fisher, Exploring the Mandelbrot set, The Science of Fractal Images (H Peitgen and D Saupe, eds.), Springer, 1989.Google Scholar
  31. FS91.
    J. Fornæss and N. Sibony, Random iterations of rational functions, Ergodic Theory Dynam. Systems 11 (1991), no. 4, 687–708.zbMATHMathSciNetGoogle Scholar
  32. Fur07.
    M. Furer, Faster integer multiplication, Proceedings of Thirty-Ninth ACM Symposium on Theory of Computing (STOC 2007), 2007.Google Scholar
  33. GMSM04.
    V. Gutlianski, O. Martio, T. Sugawa, and Vuorinen M., On the degenerate Beltrami equation, Transactions of the Amer. Math. Soc. 357 (2004), no. 3, 875–900.CrossRefGoogle Scholar
  34. Grz55.
    A. Grzegorczyk, Computable functionals, Fund. Math. 42 (1955), 168–202.zbMATHMathSciNetGoogle Scholar
  35. Her85.
    M. Herman, Are there critical points on the boundaries of singular domains?, Com-mun. Math. Phys. 99 (1985), no. 4, 593–612.zbMATHCrossRefMathSciNetGoogle Scholar
  36. Her86.
    ——, Conjugaison quasi symetrique des homeomorphismes du cercle a des rotations, and Conjugaison quasi symetrique des diffeomorphismes du cercle a des rotations et applications aux disques singuliers de Siegel, available from, 1986.
  37. Her05.
    P. Hertling, Is the Mandelbrot set computable?, Math. Log. Q. 51 (2005), no. 1, 5–18.zbMATHCrossRefMathSciNetGoogle Scholar
  38. IS06.
    H. Inou and M. Shishikura, Renormalization for parabolic fixed points and their perturbations.Google Scholar
  39. Ko91.
    K. Ko, Complexity theory of real functions, Birkhauser, Boston, 1991.zbMATHGoogle Scholar
  40. Ko98.
    ——, Polynomial-time computability in analysis, Handbook of Recursive Mathematics, Vol. 2: Recursive Algebra, Analysis and Combinatorics (Yu L et al Ershov, ed.), Studies in Logic and the Foundations of Mathematics, vol. 139, Elseveir, Amsterdam, 1998, pp. 1271–1317.Google Scholar
  41. Lac55.
    D. Lacombe, Extension de la notion de fonction recursive aux fonctions d'une ou plusiers variables, C. R. Acad. Sci. Paris 240 (1955), 2473–2480.Google Scholar
  42. Leh70.
    O. Lehto, Homeomorphisms with a given dilatation, Proceedings of the Fifteenth Scandinavian Congress (Oslo 1968). Lecture Notes in Mathematics, vol. 118, Springer, Berlin, 1970, pp. 58–73.CrossRefGoogle Scholar
  43. Leh71.
    ——, Remarks on generalized Beltrami equations and conformal mappings, Proceedings of the Romanian-Finnish seminar on Teichmuller spaces and quasiconfor-mal mappings (Bras¸ov, 1969), Publ. House of the Acad. of the Socialist Republic of Romania, Bucharest, 1971, pp. 203–214.Google Scholar
  44. Lyu86.
    M Lyubich, Dynamics of rational transformations: topological picture, Russian Math. Surveys 41 (1986), no. 4, 43–117.MathSciNetGoogle Scholar
  45. Lyu97.
    M. Lyubich, Dynamics of quadratic polynomials, III, Acta Math. 178 (1997), 185– 297.zbMATHCrossRefMathSciNetGoogle Scholar
  46. Lyu99.
    ——, Feigenbaum-Coullet-Tresser Universality and Milnor's Hairiness Conjecture, Annals of Math. 149 (1999), 319–420.zbMATHCrossRefMathSciNetGoogle Scholar
  47. Mar.
    D. Marshall, Numerical conformal mapping software: Zipper, Available from
  48. Mat93.
    Y Matiyasevich, Hilbert's Tenth Problem, The MIT Press, Cambridge, London, 1993.Google Scholar
  49. Maz63.
    S. Mazur, Computable Analysis, vol. 33, Rosprawy Matematyczne, Warsaw, 1963.Google Scholar
  50. Mil89.
    J. Milnor, Self-similarity and hairiness in the Mandelbrot set, Computers in Geometry and Topology (M Tangora, ed.), Lect. Notes Pure Appl. Math., vol. 114, Marcel Dekker, 1989, pp. 211–257.Google Scholar
  51. Mil06.
    ——, Dynamics in one complex variable. Introductory lectures, 3rd ed., Princeton University Press, 2006.Google Scholar
  52. MMY97.
    S. Marmi, P. Moussa, and J.-C. Yoccoz, The Brjuno functions and their regularity properties, Commun. Math. Phys. 186 (1997), 265–293.zbMATHCrossRefMathSciNetGoogle Scholar
  53. Moo90.
    Cristopher Moore, Unpredictability and undecidability in dynamical systems, Phys. Rev. Lett. 64 (1990), no. 20, 2354–2357.zbMATHCrossRefMathSciNetGoogle Scholar
  54. Pap94.
    C. M. Papadimitriou, Computational complexity, Addison-Wesley, Reading, Massachusetts, 1994.Google Scholar
  55. Pet96.
    C. Petersen, Local connectivity of some Julia sets containing a circle with an irrational rotation, Acta Math. 177 (1996), 163–224.zbMATHCrossRefMathSciNetGoogle Scholar
  56. Pom92.
    C. Pommerenke, Boundary behaviour of conformal maps, Springer-Verlag, 1992.Google Scholar
  57. Pos36.
    E. Post, Finite combinatory processes - Formulation 1, Journal of Symbolic Logic 1 (1936), 103–105.Google Scholar
  58. PZ04.
    C. Petersen and S. Zakeri, On the Julia set of a typical quadratic polynomial with a Siegel disk, Ann. of Math. 159 (2004), no. 1, 1–52.zbMATHMathSciNetCrossRefGoogle Scholar
  59. Ret05.
    R. Rettinger, A fast algorithm for Julia sets of hyperbolic rational functions., Electr. Notes Theor. Comput. Sci. 120 (2005), 145–157.CrossRefMathSciNetGoogle Scholar
  60. RW03.
    R. Rettinger and K. Weihrauch, The computational complexity of some Julia sets., Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9– 11, 2003, San Diego, CA, USA, 2003, pp. 177–185.Google Scholar
  61. RZ04.
    S. Rohde and M. Zinsmeister, Variation of the conformal radius, J. Anal. Math. 92 (2004), 105–115.zbMATHCrossRefMathSciNetGoogle Scholar
  62. Sie42.
    C. Siegel, Iteration of analytic functions, Ann. of Math. 43 (1942), no. 2, 607–612.CrossRefMathSciNetGoogle Scholar
  63. Sip05.
    M. Sipser, Introduction to the Theory of Computation, second edition, PWS Publishing Company, Boston, 2005.Google Scholar
  64. Sør98.
    D. Sørensen, Describing quadratic Cremer point polynomials by parabolic perturbations, Ergodic Theory Dynam. Systems 18 (1998), no. 3, 739–758.CrossRefMathSciNetGoogle Scholar
  65. Sul83.
    D. Sullivan, Conformal dynamical systems, Geometric Dynamics (Palis, ed.), Lecture Notes Math., vol. 1007, Springer-Verlag, 1983, pp. 725–752.Google Scholar
  66. Thu.
    W Thurston, On the combinatorics and dynamics of iterated rational maps, Preprint.Google Scholar
  67. Tur36.
    A. M. Turing, On computable numbers, with an application to the Entscheidungsprob-lem, Proceedings, London Mathematical Society (1936), 230–265.Google Scholar
  68. Wei00.
    K. Weihrauch, Computable Analysis, Springer-Verlag, Berlin, 2000.zbMATHGoogle Scholar
  69. Wey24.
    H. Weyl, Randbemerkungen zu Hauptproblemen der Mathematik, II, Fundamentalsatz der Algebra and Grundlagen der Mathematik, Math. Z. 20 (1924), 131–151.CrossRefMathSciNetGoogle Scholar
  70. Yam99.
    M. Yampolsky, Complex bounds for renormalization of critical circle maps, Erg. Th. & Dyn. Systems 19 (1999), 227–257.zbMATHCrossRefMathSciNetGoogle Scholar
  71. Yam02.
    M Yampolsky, Hyperbolicity of renormalization of critical circle maps, Publ. Math. Inst. Hautes Études Sci. 96 (2002), 1–41.zbMATHMathSciNetGoogle Scholar
  72. Yam08.
    M. Yampolsky, Siegel disks and renormalization fixed points. “Holomorphic Dynamics and Renormalization: A Volume in Honour of John Milnor's 75th Birthday”. Fields Institute Communications, 53 (2008)Google Scholar
  73. Yoc95.
    J.-C. Yoccoz, Petits diviseurs en dimension 1, S.M.F., Astérisque 231 (1995).Google Scholar
  74. YZ01.
    M. Yampolsky and S. Zakeri, Mating Siegel quadratic polynomials, J. Amer. Math. Soc. 14 (2001), no. 1, 25–78.zbMATHCrossRefMathSciNetGoogle Scholar
  75. Zho98.
    N. Zhong, Recursively enumerable subsets of ℝ q in two computing models: Blum-Shub-Smale machine and Turing machine, Theor. Comp. Sci. 197 (1998), 79–94.zbMATHCrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2009

Personalised recommendations