Unpredictability and Undecidability in Dynamical Systems

Physical Review Letters 64 (1990) 2354-2357

We show that motion with as few as three degrees of freedom (for instance, a particle moving in a three-dimensional potential) can be equivalent to a Turing machine, and so be capable of universal computation. Such systems possess a type of unpredictability qualitatively stronger than that which has been previously discussed in the study of low-dimensional chaos: even if the initial conditions are known exactly, virtually any question about their long-term dynamics are undecidable.

Click here to download (gzipped archive of .ps files).

Cris Moore <moore@santafe.edu>