• English
    • français
  • Help
  •  | 
  • Contact
  •  | 
  • About
  •  | 
  • Login
  • HAL portal
  •  | 
  • Pages Pro
  • EN
  •  / 
  • FR
View Item 
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Unpredictability and computational irreducibility
  • BibTeX
  • CSV
  • Excel
  • RIS

Document type :
Partie d'ouvrage
DOI :
10.1007/978-3-642-35482-3
Title :
Unpredictability and computational irreducibility
Author(s) :
Zwirn, Hervé [Auteur]
Institut d'Histoire et de Philosophie des Sciences et des Techniques [IHPST]
Delahaye, Jean-Paul [Auteur]
Systèmes Multi-Agents et Comportements [SMAC]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Scientific editor(s) :
Hector Zenil, ed.
Book title :
Irreducibility and Computational Equivalence: 10 Years After Wolfram's A New Kind of Science (Emergence, Complexity and Computation)
Publisher :
Springer
Publication date :
2013
ISBN :
978-3-642-35481-6
English keyword(s) :
Complexity
logical depth
cellular automata
irreducibility
computation
HAL domain(s) :
Sciences de l'Homme et Société/Histoire, Philosophie et Sociologie des sciences
English abstract : [en]
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 ...
Show more >
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.Show less >
Language :
Anglais
Audience :
Non spécifiée
Popular science :
Non
Collections :
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Source :
Harvested from HAL
Université de Lille

Mentions légales
Université de Lille © 2017