THEOREM 2. 2 For all parameters c,
the filled Julia set Kc:
THEoREM 2. 2 For all parameters c,
the filled Julia set Kc is computable.
is the Universe a computer?
We have explored three examples of
dynamical systems: The first, harmonic oscillator Xosc, is simple; its behavior
can be calculated in closed form, and
we can answer pretty much any question about the long-term behavior
of the harmonic oscillator computationally. The second, computer system Xcomp, is at the opposite extreme;
predicting it is computationally hard,
and it is (relatively) easy to show it is
computationally hard through a reduction to the Halting Problem. The
third, complex dynamics, requires an
involved approach. For some (in fact,
most) parameters c, the long-term
behavior of the system Xc is easy in
almost any sense imaginable. Showing there are parameters c for which
no amount of computational power
suffices to compute the Julia set Jc required a full understanding of the underlying dynamical system developed
over nearly a century.
Our experience with the comput-
ability of Julia sets, as well as the rela-
tive success of the field of automated
verification at solving undecidable
problems in practice, 5 indicates there
is likely to be a gap between comput-
ability in dynamics in the worst case
and in the typical case. This gap means
it is possible that while questions sur-
rounding many natural systems (such
as the N-body problem and protein as-
sembly) are provably noncomputable
in the worst case, a typical case in prac-
tice is tractable.
A related interesting possibility
is that noncomputable structures in
many systems are too delicate to survive the random noise present in all
natural systems. Noise is generally
viewed as a “prediction destroying”
force, in that making predictions in
the presence of noise is computationally more difficult. On the other hand,
if we are interested in predicting the
statistical distribution of possible future states, then noise may actually
make the task easier. It is likely there
are natural systems that (if implemented with no noise) would be computationally impossible to predict but
where the presence of noise makes
statistical predictions about the system computationally tractable.
Another lesson from the study of the
computational properties of Julia sets is
that mapping out which of the Julia sets
Jc are and which are not computable
requires a nuanced understanding of
the underlying dynamical system. It is
likely this is the case with other natural
dynamical systems; the prerequisite to
understanding its computational prop-
erties would be understanding its other
properties. Indeed, understanding the
role (non)computability and compu-
tational universality play in natural
dynamical systems probably requires
significant advances in both real com-
putation and dynamical systems. The
role of computational universality—the
ability of natural systems to simulate ge-
neric computation—in nature is there-
fore likely to remain one of the most
tantalizing open problems in natural
philosophy for some time to come.
The following references include extensive bibliographies for readers interested in computation over the reals;
computability of real numbers was first
discussed in Turing’s seminal paper, 4
which also started the field of computability. There are two main modern
visions on computability over the real
numbers: computable analysis and the
Blum-Shub-Smale (BSS) framework.
My presentation here is fully based on
the framework of computable analysis, as presented in-depth by Weihrauch. 6 The BSS framework is more
closely related to algebraic geometry
and presented by Blum et al. 1 I focused
on computable analysis, as it appears
more appropriate for the study of the
computational hardness of natural
problems over the reals. The results
on the computability and complexity
of Julia sets was presented by Braverman and Yampolsky. 2 Computational
universality of dynamical systems is
discussed in several sources, including
Moore3 and Wolfram, 7 but many basic
questions remain open.
Work on this article has been supported in part by an Alfred P. Sloan
Fellowship, National Science Foundation awards CCF-0832797 and CCF-
1149888, and a Turing Centenary
Fellowship from the John Templeton
1. blum, l., Cucker, f., Shub, m., and Smale, S.
Complexity and Real Computation. Springer-Verlag,
new york, 1998.
2. braverman, m. and yampolsky, m. Computability of
Julia Sets. Springer Verlag, berlin heidelberg, 2009.
3. moore, C. unpredictability and undecidability in
dynamical systems. Physical Review Letters 64, 20
(may 1990), 2354–2357.
4. turing, a.m. on computable numbers, with an
application to the entscheidungsproblem. Proceedings
of the London Mathematical Society 42, 2 (nov. 12,
5. Vardi, m. Solving the unsolvable. Commun. ACM 54, 7
(July 2011), 5.
6. weihrauch, k. Computable Analysis. Springer-Verlag,
7. wolfram, S. A New Kind of Science. wolfram media,
Champaign, Il, 2002.
Mark Braverman ( firstname.lastname@example.org) is an
assistant professor in the Department of Computer
Science at Princeton university, Princeton, nJ.
© aCm 0001-0782/13/09 $15.00
figure 5. Example outcomes of the heuristic algorithm with c ≈ –0.126 + 0.67i and M = 25,
M = 100, and M = 3,000 iteration. note with the lower values of M the fjords do not reach all
the way to the center since the points close to the center do not have time to “escape” in M
iterations. the difficulty selecting a “large enough” M is a crucial obstacle in computing the
exterior of the filled Julia set Kc.
M = 25 M = 100 M = 3,000