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.
2019
9783030152765
9783030152772
Principle of computational equivalence; computational universality; computational undecidability; discrete dynamical system; emulation; state classification problem
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11584/270034
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact