Natural complexity, computational complexity and depth

DOI10.1063/1.3634009MaRDI QIDQ5264347zbMATH OpenOpenAlexWikidataFDO

Authors J. Machta

Publication date 27 July 2015

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

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

Mathematics Subject Classification ID

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

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.

Recommendations

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

Cites work

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

Cited in

(4)

• Computational depth and reducibility
• scientific article; zbMATH DE number 4093436 (Why is no real title available?)
• How should complexity scale with system size?
• scientific article; zbMATH DE number 7139948 (Why is no real title available?)

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)