I have seen the claim in a recent unpublished paper that chaotic dynamics are necessarily uncomputable. This follows, they argue, from the sensitivity to initial conditions shown in chaotic systems. This glib identity between chaos and computability struck me as simplistic, but I have not found a good discussion of the topic that I trust.
I found one discussion by Svozil (1989) 'Are chaotic systems dynamically random?' which claims there exist four types of chaos, depending on whether the initial conditions are computable, and whether the evolution of the system is computable. This generates four possibilities: for instance Chaos of Type I is "generated by a computable evolution of a system with uncomputable...initial values" (p 4). The fourth type is the chaotic dynamics produced when both initial conditions and evolution of the system are computable. This would suggest that chaos does not imply uncomputability (of either type).
Is this division of possibilities generally accepted? More to the point, is the relationship between chaos and computability worked out sufficiently so there is now an obvious answer to my question?
Karl Svozil. Are chaotic systems dynamically random?, Phys. Lett. A 140, 5-9 (1989) http://tph.tuwien.ac.at/~svozil/publ/1989-dyn.pdf
I should have been more clear that my question is about chaos in continuous systems, not discrete systems.
Also, after asking this question I found the following potentially relevant papers:
- Corless (1994) What good are numerical simulations of chaotic dynamical systems? Computers Math. Applic. 28: 107-121.
- Yao (2010) Computed chaos or numerical errors. Nonlinear Analysis 2010: 109-126.
- Lia (2014) A comment on the arguments about the reliability and convergence of chaotic simulations. http://arxiv.org/abs/1401.0256v1.
Via discussions below, there is one subquestion that has emerged that seems to identify the crux of the issue with more precision than my original question:
Assume (a) that any numerical simulation of the solution of continuous chaotic dynamical system X will necessarily strongly diverge from the actual solution (at some point in time in the simulation).
Is it true, in any of the well-defined senses of 'computable' from the theory of computation, that the behavior of system X is uncomputable? If no, then the claim that chaotic systems are uncomputable, in the sense usually intended, seems false as a mathematical claim.
If yes, then two subquestions. 1. For what senses of computable is the system uncomputable? 2. Is assumption (a) true for any interesting scientific model (e.g., a specific model from neuroscience that people actually use)?
Still waiting for an answer to this question. I did get a response from a philosopher who didn't answer it but suggested a book. Here is his message to me:
You may want to have a look at the book "Complexity and Real Computation" by Blum, Cucker, Shub & Smale. I still have to real most of it, but I think you will find their analysis of computability helpful. Their don't specifically address chaotic dynamics, but they thoroughly analyze the relation between condition numbers (chaotic problems are tough precisely because they're ill-conditioned), complexity, and computability (in Turing's sense and for arbitrary rings and fields).
I haven't looked at the book yet.