Unpredictability and computational irreducibility - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Chapitre D'ouvrage Année : 2013

Unpredictability and computational irreducibility

Résumé

We explore several concepts for analyzing the intuitive notion of computational irreducibility and we propose a robust formal definition, first in the field of cellular automata and then in the general field of any computable function f from N to N. We prove that, through a robust definition of what means "to be unable to compute the nth step without having to follow the same path than simulating the automaton or the function", this implies genuinely, as intuitively expected, that if the behavior of an object is computationally irreducible, no computation of its nth state can be faster than the simulation itself.
Fichier non déposé

Dates et versions

halshs-00775748 , version 1 (16-01-2013)

Identifiants

Citer

Hervé Zwirn, Jean-Paul Delahaye. Unpredictability and computational irreducibility. Hector Zenil, ed. Irreducibility and Computational Equivalence: 10 Years After Wolfram's A New Kind of Science (Emergence, Complexity and Computation), Springer, pp.273-295, 2013, 978-3-642-35481-6. ⟨10.1007/978-3-642-35482-3⟩. ⟨halshs-00775748⟩
285 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More