Unpredictability and computational irreducibility

DOI10.1007/978-3-642-35482-3_19zbMATH Open1298.68188arXiv1111.4121OpenAlexW1516908437MaRDI QIDQ2929348FDOQ2929348

Hervé P. Zwirn, Jean-Paul Delahaye

Publication date: 12 November 2014

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

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.

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

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
• Computational processes and incompleteness

zbMATH Keywords

complexitycellular automatacomputationirreducibilitylogical depth

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Numerical evaluation of algorithmic complexity for short strings: a glance into the innermost structure of randomness
• Title not available (Why is that?)
• Algorithmic Randomness and Complexity
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Chaos in Dynamical Systems
• Title not available (Why is that?)
• The definition of random sequences
• Statistical mechanics of cellular automata
• Computational Complexity
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Classical recursion theory. The theory of functions and sets of natural numbers
• Effective Complexity and Its Relation to Logical Depth
• Title not available (Why is that?)
• From Instability to Intelligence
• Depth as randomness deficiency
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (2)

• Unresolved computation and optimal predictions
• 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)