Fiche du document
2013
- handle: 10670/1.r1s7db
- isbn: 978-3-642-35481-6
- halshs: halshs-00775748
- doi: 10.1007/978-3-642-35482-3
Ce document est lié à :
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-642-35482-3
Sujets proches
Iterative circuit computers Tessellation structures (Automata) Computers, Iterative circuit Structures, Tessellation (Automata)Citer ce document
Hervé Zwirn et al., « Unpredictability and computational irreducibility », HAL-SHS : histoire, philosophie et sociologie des sciences et des techniques, ID : 10.1007/978-3-642-35482-3
Métriques
Partage / Export
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.