7
$\begingroup$

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?

Reference
Karl Svozil. Are chaotic systems dynamically random?, Phys. Lett. A 140, 5-9 (1989) http://tph.tuwien.ac.at/~svozil/publ/1989-dyn.pdf

Edit 1
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.

Edit 2
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)?

Edit 3

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.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ ATW x -> 4x(1-x) is chaotic, verified in Matlab (eyeballing it) even for rational initial values. So surely not? $\endgroup$ – Matt Phillips Jan 29 '14 at 21:14
  • $\begingroup$ Matt: a simulation showing chaotic behavior seems insufficient to show that a chaotic dynamical system is computable. The question is whether the simulation can be accurate, given the potential for errors to blow up, as I discussed below (math.stackexchange.com/questions/652731/…) in more detail. (Plus, simulation can actually induce chaotic behavior in nonchaotic systems: sciencedirect.com/science/article/pii/089812219400188X). $\endgroup$ – neuronet Jan 30 '14 at 15:21
  • 1
    $\begingroup$ See also math.stackexchange.com/a/334055/589. $\endgroup$ – lhf Jan 30 '14 at 16:04
  • 1
    $\begingroup$ I would love to answer this question, but I think it is just too vague. What is "chaos"? Which of the many notions of "computable" is intended? $\endgroup$ – Carl Mummert Feb 1 '14 at 13:19
  • $\begingroup$ @CarlMummert: yes that is an issue. Claims like "Chaotic systems are uncomputable" typically are thrown out there without reference, proof, or definition. That is why I am posting here. My question is whether the two domains, and relation between them, are worked out enough to make sense of the generic claim (e.g., if it is, the disambiguation would have to be part of the answer: e.g., using this standard sense of chaos, and this sense of 'uncomputability of the evolution of a dynamical system' (Svozil 1989), the claim is false. $\endgroup$ – neuronet Feb 1 '14 at 16:44
4
$\begingroup$

Choaticity in computable systems are a well known topic in theoretical computer science. For example, you can read numerous articles on cellular automata and their computational behaviour. A chaotic behaviour will be defined using some usual topology and it can be proved that some cellular automata are chaotic (it means there are some butterfly effects). But they are entirely computable, as well as initial conditions.

From a purely computability point of view, chaoticity can appear as soon as you can't predict some behaviour. Many problems are computable but some behaviour (like the halting problem) can't be predicted.

An example of that is the n-body problem in physics. Computations can be made to define the next state of the system, but you can't answer some question like "Will this planet crash into this other one ?"

So, to my point of view, chaotic systems can be computable, but you can ask uncomputable questions about them.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Great point about discrete chaos. My main concern is for continuous systems. For that, you mentioned an uncomputable n-body problem:"Have we not predicted a collision because there will never be a collision, or because we haven't run the simulation long enough?" Good one! You also suggest that for the n-body problem the evolution of the system is computable. Is that a well-known result where I could get a reference? I ask b/c there might be noncomputable irrational numbers as initial conditions, which may make the evolution of the system uncomputable via numerical simulation. Am I muddled? $\endgroup$ – neuronet Jan 28 '14 at 20:26
  • $\begingroup$ @neuronet computable reals just mean (here) that you can compute them with as much precision as you want, as long as you know initial conditions with as much precision as you need. This is true for any mechanics model (newtonian or relativistic). The problem is that in reality, you can measure values with only limited precision. It does not make sens to speak about uncomputable initial conditions : You can't measure them, and in fact, you can't even say that "real" ($\mathbb R$) values exist in the reality. $\endgroup$ – Xoff Jan 28 '14 at 21:19
  • $\begingroup$ Xoff let x be one of the (uncountably infinite) uncomputable reals. Set x as the initial condition of some variable in an n-body chaotic system. Is the evolution of the system computable in this case? If not, then it seems we cannot say the n-body problem is generically computable. Note this a mathematical question, not a physics/philosophy question about whether reality can instantiate uncomputable numbers. Relevant post: math.stackexchange.com/questions/58036/… $\endgroup$ – neuronet Jan 29 '14 at 2:16
  • 1
    $\begingroup$ @neuronet The problem is not a problem of uncomputability, but of accessibility. If you can't access the value (for example because of the way it is described) in a chaotic system, the simulation will diverge if you use something close, yes, even in computable system like some cellular automata. So yes, for an uncomputable starting condition, you can't compute the trajectory in such system, even something close. $\endgroup$ – Xoff Jan 29 '14 at 16:35
  • 2
    $\begingroup$ @neuronet "In a nonchaotic system, the solution will be close if you pick an initial condition close to the noncomputable number." False, topological mixing is also required. But as to your question, is the idea of doing a computation on an uncomputable input even coherent? Not if computable means Turing-computable. $\endgroup$ – Matt Phillips Jan 29 '14 at 20:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.