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

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.
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
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: http://hdl.handle.net/11584/270034
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact