[Colloquium] Mark Braverman, University of Toronto- TTI-C Talk

[Julia MacGlashan]

When:              Friday, April 11 @ 10:00am

 

Where:            TTI-C Conference Room

 

Who:                Mark Braverman, University of Toronto

 

Topic:              Computability and Complexity of Julia sets

 

 

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.

 

Contact:          Nikhil Devanur, TTI-C         nikhil at tti-c.org
834-3541 

 

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20080408/bcb89ccc/attachment-0001.html