[FOM] Julia sets and computability models

Stephen Cook sacook at cs.toronto.edu
Thu Feb 17 11:17:03 EST 2005

I would like to draw attention to several recent papers on
computability and complexity in analysis, authored or coauthored
by my PhD student Mark Braverman.  These papers are available
on Mark's web site at

"On the complexity of real functions" is a very nice survey paper
comparing various "bit complexity" models and variations on the
Blum/Shub/Smale model of computation, both for computing real functions
and recognizing (or "drawing") subsets of R^n, such as the Mandelbrot set.

"Filled Julia sets with empty interior are computable" and
"On computational complexity of Siegel Julia sets", coauthored
with Ilia Binder and Michael Yampolsky,  come close to
classifying all Julia sets with respect to computabililty, using
recent deep theorems in dynamical systems.

Mark's MSc thesis (also available) compares computational models,
and proves that all hyperbolic Julia sets are polynomial time computable
(using a standard computation model based on "drawing" arbitrarily
fine details of the set), a result proved independently by R. Rettinger.

Stephen Cook

More information about the FOM mailing list