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 | Size | Format | |
---|---|---|---|
Giunti_2019_Are_dynamically_undecidable_systems_ubiquitous.pdf Solo gestori archivio
Description: Versione pubblicata del contributo in volume
Type: versione editoriale
Size 867.77 kB
Format Adobe PDF
|
867.77 kB | Adobe PDF | & nbsp; View / Open Request a copy |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.