Unpredictability and undecidability in dynamical systems. (English) Zbl 1050.37510

Summary: 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 is undecidable.


37D45 Strange attractors, chaotic dynamics of systems with hyperbolic behavior
03D10 Turing machines and related notions
37E99 Low-dimensional dynamical systems
Full Text: DOI


[1] S. Wolfram, Commun. Math. Phys. 96 pp 15– (1984) · Zbl 0587.68050 · doi:10.1007/BF01217347
[2] S. Wolfram, Phys. Rev. Lett. 54 pp 735– (1984) · doi:10.1103/PhysRevLett.54.735
[3] S. Omohundro, Physica (Amsterdam) 10D pp 128– (1984)
[4] E. Fredkin, Int. J. Theor. Phys. 21 pp 219– (1982) · Zbl 0496.94015 · doi:10.1007/BF01857727
[5] S. Smale, in: Differential and Combinatorial Topology (1963)
[6] , in: Hamiltonian Dynamical Systems (1987)
[7] P. Cvitanović, Phys. Rev. Lett. 61 pp 2729– (1988) · doi:10.1103/PhysRevLett.61.2729
[8] H. Rogers, Jr., in: Theory of Recursive Functions and Effective Computability (1967)
[9] C. Crebogi, Phys. Lett. 99A pp 415– (1983)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.