Chaos and Computation

The interesting thing about all of these models is that whenever a dynamical system is shown to be capable of universal computation, the dynamical system possess es, at least in part, chaotic dynamics. This duality of chaos and computability is primarily a result of the recursive nature of dynamical systems and computing devices. For all of these models of computation, if one were to write a "program" that attempted to answer an incomputable question, such as the Halting Problem, running the resulting program would place all of these systems into a potentially chaotic state. If these chaotic computers happen to halt, then the dynamics for the starting conditions correspond to the attractor of a fixed point. But if the chaotic computer never halts for such a question, then the system has fallen into a chaotic attractor.

many reasonable questions that one would like to ask about dynamical systems are often undecidable, in the strict sense, from the theory of computation. For example, it is, in general, not possible to definitively say that data come from a chaotic or nonchaotic source. Posing this question for a chaotic computer is akin to solving the Halting Problem. It is not even possible to determine if the state of a chaotic system will ever fall into a specific region of state space. If portions of a state space are known to eventually fall into a fixed point , then knowing this fact is equivalent to solving the Halting Problem. The reason for all of this uncertainty is related to the fact that symbolic mathematics (which can be used to formalize the questions listed above) cannot always make definitive statements about things that exist on a continuum.

(In 14. Postscript: Chaos; pp.226)