Logical Depth

Core components

• Object: typically discrete-symbol sequence or finite computational object
• Program: Turing-machine program producing the object as output
• Near-minimal program: program of length close to (within b bits of) the Kolmogorov-complexity-minimal program — Bennett uses 'b-incompressible' programs
• Logical depth at significance level b: the running time of the b-incompressible program — the computational time required to produce the object from a near-minimal description
• Distinction from Kolmogorov complexity: Kolmogorov complexity counts the program length (static information)
• logical depth counts the program running time (computational history)
• Inversion property: low logical depth for both fully random objects (cannot be compressed, so the minimal program is trivial-output, requiring no computation time) and fully ordered objects (trivial pattern production)
• high logical depth for objects requiring substantial computational derivation from compressed descriptions
• Slow-growth law (Bennett): logical depth cannot be rapidly increased by computational processes — shallow objects do not become deep through deterministic computation, only through evolutionary or learning processes that accumulate computational history over time
• Physical-complexity intuition: complex physical objects (cells, ecosystems, civilizations, libraries, computer programs) embody substantial computational history that simple measurement cannot capture but logical depth approximates
• Stability under noise: logical-depth concept has been argued by Bennett to be more stable under small perturbations than Kolmogorov complexity, since adding noise increases Kolmogorov complexity (noise is incompressible) but does not increase logical depth
• Computational-uncomputability: like Kolmogorov complexity, logical depth is uncomputable in general (no algorithm can compute logical depth of arbitrary objects)
• Distinction from Statistical Complexity and Effective Complexity: each captures different aspects of structured-process intuition with different formal foundations
• Application contexts: foundational complexity-theory discussions, biological-complexity characterization, philosophical-foundational debates about origin of complexity

Primary use case

Foundational complexity measure addressing the intuition that complex objects embody substantial computational history; applied principally in: complexity-theory foundational research, philosophical-foundational discussions of complexity and emergence, biological-complexity characterization, broader thermodynamics-of-computation research; academic and professional reference in computational complexity, statistical physics, information theory, and broader interdisciplinary complexity literature; complementary to Statistical Complexity (Crutchfield-Young), Effective Complexity (Gell-Mann), and other proposed complexity measures; intellectual foundation for slow-growth-law-based discussions of the origin of complexity in physical and biological systems; modest empirical application due to computational-uncomputability of logical depth in general — research applications use approximations and specific-case analysis rather than direct computation.

Common criticisms

• Logical Depth faces substantive challenges — the measure is computationally uncomputable in general, with no algorithm capable of computing logical depth of arbitrary objects, limiting empirical application to approximations and specific-case analysis
• the b-incompressibility threshold (programs within b bits of Kolmogorov-complexity-minimal) introduces a free parameter whose appropriate value depends on context, with different threshold choices producing different logical-depth values
• comparison with Statistical Complexity (Crutchfield-Young) and Effective Complexity (Gell-Mann) reveals different formal foundations for related intuitions, with practitioner debate about which measure is appropriate for which contexts
• the dependence on Turing-machine model produces invariance only up to additive constant, which limits cross-system comparison precision
• the slow-growth law has substantial intuitive appeal but its formal implications for biological-complexity origin have been argued by some critics to overstate what the formal measure actually establishes — whether biological complexity is genuinely logical-depth-rich requires empirical demonstration that the formal framework does not directly provide
• the framework's adoption outside theoretical-complexity research community has been limited, with biology, physics, and computer-science applications more often using simpler complexity proxies
• the foundational philosophical question of whether logical depth captures the 'right' notion of complexity remains contested, with alternative formalizations (thermodynamic depth, sophistication, algorithmic mutual information) competing for the same intuitive territory
• modern machine-learning approaches to complexity measurement (neural-network-based complexity estimators, transformer-based language-model complexity proxies) have produced fruitful empirical applications without formally connecting to logical depth
• the relationship between logical depth and physically-realized computational history (the fact that physical objects do embody substantial computational history through evolution, learning, manufacturing) is intuitively suggestive but the formal correspondence between the abstract Turing-machine-running-time measure and physically-realized computation remains methodologically complex.