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?
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-3429Wesley Calvert's Web Page