Are dynamically undecidable systems ubiquitous?

Marco Giunti

2019-01-01

---

Abstract

Stephen Wolfram has maintained that almost any system whose behavior is not obviously simple is computationally universal and, consequently, its long term behavior is undecidable. Wolfram's tenet is a direct consequence of his Principle of Computational Equivalence (PCE). In this paper, I propose an independent argument for the ubiquity of computational universality and, as a consequence, dynamical undecidability as well. My argument does not presuppose PCE and, in essence, it is based on the recognition of two facts: (1) the existence of a strong structural similarity between the transition graphs of any two computational systems; (2) the mapping needed for computational universality is emulation, which is itself a quite weak structural mapping.