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.
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.File | Dimensione | Formato | |
---|---|---|---|
Giunti_2019_Are_dynamically_undecidable_systems_ubiquitous.pdf
Solo gestori archivio
Descrizione: Versione pubblicata del contributo in volume
Tipologia:
versione editoriale (VoR)
Dimensione
867.77 kB
Formato
Adobe PDF
|
867.77 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.