Skip to content. Skip to navigation
CIM Menus

School of Computer Science Seminar Series

Computability and Complexity of Julia Sets

Mark Braverman < >
Department of Computer Science University of Toronto

February 18, 2008 at  9:30 AM
George Zames Room MC437

Studying dynamical systems is key to understanding a wide range of phenomena ranging from planets' movement to climate patterns to market dynamics. Various numerical tools have been developed to address specific questions about dynamical systems, such as predicting the weather or planning the trajectory of a satellite. However, the theory of computation behind these problems appears to be very difficult to develop. While we have vast knowledge about computability and complexity of discrete problems, little is known about computability of even the most natural problems arising from dynamical systems.

The focus of our study is dynamical systems that arise from iterating quadratic polynomials on the complex plane. They give rise to the amazing variety of fractals known as Julia sets, and are closely connected to the Mandelbrot set. Julia sets are perhaps the most drawn objects in Mathematics due to their fascinating fractal structure. The theory behind them is even more fascinating, and the dynamical systems generating them are in many ways archetypal.

In this talk we discuss what it means for a planar set to be computable. We then present a variety of recent results, both positive and negative, on the computability and complexity of Julia sets. In particular we show that while the vast majority of Julia sets are computable - many even in polynomial time, some are as hard to compute as the Halting Problem and will never be drawn. The work paves the way to understanding computational properties of more complicated dynamical systems.

Mark Braverman studied at the Israel Institute of Technology (Technion), Yale University, and will be graduating in April 2008 from the University of Toronto.