Unpredictability and computational irreducibility

DOI10.1007/978-3-642-35482-3_19MaRDI QIDQ2929348zbMATH OpenOpenAlexFDO

Authors Hervé P. Zwirn, Jean-Paul Delahaye

Publication date 12 November 2014

Published in Emergence, Complexity and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.4121

zbMATH Keywords

complexitycellular automatacomputationirreducibilitylogical depth

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Abstract: 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.

Recommendations

• Computational irreducibility and computational analogy
• The slowdown theorem: a lower bound for computational irreducibility in physical systems
• Unpredictability and undecidability in dynamical systems
• scientific article; zbMATH DE number 4089442
• Computational processes and incompleteness

Cites work

• scientific article; zbMATH DE number 1818513 (Why is no real title available?)
• scientific article; zbMATH DE number 4093436 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 1548484 (Why is no real title available?)
• scientific article; zbMATH DE number 1911266 (Why is no real title available?)
• scientific article; zbMATH DE number 773150 (Why is no real title available?)
• scientific article; zbMATH DE number 5018180 (Why is no real title available?)
• scientific article; zbMATH DE number 5252406 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3305097 (Why is no real title available?)
• scientific article; zbMATH DE number 3076934 (Why is no real title available?)
• A general notion of useful information
• Algorithmic randomness and complexity.
• Chaos in Dynamical Systems
• Classical recursion theory. The theory of functions and sets of natural numbers
• Computational Complexity
• Depth as randomness deficiency
• Effective Complexity and Its Relation to Logical Depth
• From Instability to Intelligence
• Numerical evaluation of algorithmic complexity for short strings: a glance into the innermost structure of randomness
• Statistical mechanics of cellular automata
• The definition of random sequences
• Universality in elementary cellular automata

Cited in

(5)

• Abduction, unpredictability and Garden of Eden
• Unresolved computation and optimal predictions
• The slowdown theorem: a lower bound for computational irreducibility in physical systems
• Computational irreducibility and computational analogy
• Condensed Unpredictability

This page was built for publication: Unpredictability and computational irreducibility

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2929348)