Limits of Computation in Dynamical Systems and Chaos

Let X be a topological space --- even a very nice one; for instance, it could be second countable, a metric space, and complete with respect to its metric. We can let f be a function from X to X, even a very nice one. Then we take a point a in X and look at the sequence a, f(a), f(f(a)), f(f(f(a))), .... The behavior of this sequence can be very subtle, even for very simple choices of X and f.

Which are the periodic (or preperiodic) points of a dynamical system? There was significant work by Braverman and Yampolsky demonstrating that certain Julia sets are computable and others aren't, but this covered a relatively small set of possible dynamical systems.

Of course, now that people often treat topoligical spaces of the kind we have in mind as structures --- not unlike a group or a field --- we can also ask about these things in the context of computable model theory. How do the dynamics of a point relate to its Scott rank, for instance? Or how does the dynamical complexity relate to the categoricity of the system. Of course, some of these problems have answers that would be, at least, unsurprising. There are many still to be asked, though.

More broadly, can dynamical aspects of a system (Lyapunov exponent, for instance) be connected to algorithmic randomness? If f is ergodic, or mixing, or turbulent, for instance, can we conclude anything about the algorithmic randomness (Kolmogorov Complexity, normality, etc. of the orbits?

Send correspondence to
Department of Mathematics
Mail Code 4408
Southern Illinois University
1245 Lincoln Drive
Carbondale, Illinois 62901
Office: (618) 453-6582
Fax: (618) 453-5300
Home: (618) 985-3429
Wesley Calvert's Web Page