On computational irreducibility and the predictability of complex physical systems

Abstract

Using elementary cellular automata (CA) as an example, we show how to coarse-grain CA in all classes of Wolfram's classification. We find that computationally irreducible (CIR) physical processes can be predictable and even computationally reducible at a coarse-grained level of description. The resulting coarse-grained CA which we construct emulate the large-scale behavior of the original systems without accounting for small-scale details. At least one of the CA that can be coarse-grained is irreducible and known to be a universal Turing machine.

4 pages, 2 figures, to be published in PRL

References in corpus (1)

• Renormalization group and perfect operators for stochastic differential equations

Cited by in corpus (30)

• Predicting the long time dynamic heterogeneity in a supercooled liquid on the basis of short time heterogeneities
• Generalized logistic growth modeling of the COVID-19 outbreak: comparing the dynamics in the 29 provinces in China and in the rest of the world
• Automatic Filters for the Detection of Coherent Structure in Spatiotemporal Systems
• Coarse-graining of cellular automata, emergence, and the predictability of complex systems
• Complementarity in classical dynamical systems
• Self-Organization and Artificial Life
• Law without law: from observer states to physics via algorithmic information theory
• $1/f^{\alpha }$ spectra in elementary cellular automata and fractal signals
• Optimal high-level descriptions of dynamical systems
• Illusory versus Genuine Control in Agent-Based Games
• Foreword: A Computable Universe, Understanding Computation and Exploring Nature As Computation
• Space-bounded Church-Turing thesis and computational tractability of closed systems
• Causal Geometry
• Unpredictability of AI
• Time-evolution of the Rule 150 cellular automaton activity from a Fibonacci iteration
• Semipredictable dynamical systems
• Undecidability in Physics: a Review
• Interdisciplinarity in Socio-economics, mathematical analysis and predictability of complex systems
• Models of the "Universe" and a Closure Principle
• Information, complexity, brains and reality (Kolmogorov Manifesto)
• A General Strategy for Physics-Based Model Validation Illustrated with Earthquake Phenomenology, Atmospheric Radiative Transfer, and Computational Fluid Dynamics
• Non-invertible transformations and spatiotemporal randomness
• Visualizing computation in large-scale cellular automata
• Reality as Simplicity
• Operator representation and logistic extension of elementary cellular automata
• Renormalisation of Quantum Cellular Automata
• On Function Description
• On the algorithmic descriptive complexity of attractors in topological dynamics
• An Improved Algorithm for Coarse-Graining Cellular Automata
• Bulking II: Classifications of Cellular Automata