Self-referential basis of undecidable dynamics: from The Liar Paradox and The Halting Problem to The Edge of Chaos
arXiv:1711.02456 · doi:10.1016/j.plrev.2018.12.003
Abstract
In this paper we explore several fundamental relations between formal systems, algorithms, and dynamical systems, focussing on the roles of undecidability, universality, diagonalization, and self-reference in each of these computational frameworks. Some of these interconnections are well-known, while some are clarified in this study as a result of a fine-grained comparison between recursive formal systems, Turing machines, and Cellular Automata (CAs). In particular, we elaborate on the diagonalization argument applied to distributed computation carried out by CAs, illustrating the key elements of Gödel's proof for CAs. The comparative analysis emphasizes three factors which underlie the capacity to generate undecidable dynamics within the examined computational frameworks: (i) the program-data duality; (ii) the potential to access an infinite computational medium; and (iii) the ability to implement negation. The considered adaptations of Gödel's proof distinguish between computational universality and undecidability, and show how the diagonalization argument exploits, on several levels, the self-referential basis of undecidability.
arXiv comment25 pages
References in corpus (7)
- Local information transfer as a spatiotemporal filter for complex systems
- Automatic Filters for the Detection of Coherent Structure in Spatiotemporal Systems
- Coarse-graining of cellular automata, emergence, and the predictability of complex systems
- Upper Bound on the Products of Particle Interactions in Cellular Automata
- Decidability and Universality in Symbolic Dynamical Systems
- A Concrete View of Rule 110 Computation
- Computation and Universality: Class IV versus Class III Cellular Automata
Cited by in corpus (5)
- Algorithmic Networks: central time to trigger expected emergent open-endedness
- Relating complexities for the reflexive study of complex systems
- Learning to Optimize with Dynamic Mode Decomposition
- The Undecidable Charge Gap and the Oil Drop Experiment
- Bounded rationality for relaxing best response and mutual consistency: The Quantal Hierarchy model of decision-making