Natural complexity, computational complexity and depth

DOI10.1063/1.3634009zbMATH Open1317.70016arXiv1111.2845OpenAlexW3100772991WikidataQ51605804 ScholiaQ51605804MaRDI QIDQ5264347FDOQ5264347

Authors: J. Machta 

Publication date: 27 July 2015

Published in: Chaos: An Interdisciplinary Journal of Nonlinear Science (Search for Journal in Brave)

Abstract: Depth is a complexity measure for natural systems of the kind studied in statistical physics and is defined in terms of computational complexity. Depth quantifies the length of the shortest parallel computation required to construct a typical system state or history starting from simple initial conditions. The properties of depth are discussed and it is compared to other complexity measures. Depth can only be large for systems with embedded computation.

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

Recommendations

• scientific article; zbMATH DE number 4093436
• Depth as randomness deficiency
• scientific article; zbMATH DE number 4072382
• Recursive computational depth.
• Recursive computational depth

Mathematics Subject Classification ID

Transition to stochasticity (chaotic behavior) for nonlinear problems in mechanics (70K55)

Cites Work

• Majority-vote cellular automata, Ising dynamics, and \(\mathbf P\)-completeness
• Existence of a phase-transition in a one-dimensional Ising ferromagnet
• Title not available (Why is that?)
• Toward a quantitative theory of self-generated complexity
• Predictability, complexity, and learning
• Complexity through nonextensivity
• Title not available (Why is that?)
• Excess entropy in natural language: present state and perspectives
• What is complexity?
• Effective Complexity and Its Relation to Logical Depth
• Sampling chaotic trajectories quickly in parallel
• The computational complexity of the Lorentz lattice gas
• Universal computation and physical dynamics
• The computational complexity of pattern formation
• The parallel complexity of growth models
• The computational complexity of generating random fractals

Cited In (4)

• Computational depth and reducibility
• Title not available (Why is that?)
• How should complexity scale with system size?
• Title not available (Why is that?)

This page was built for publication: Natural complexity, computational complexity and depth

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