Logical Depth

Logical depth is a measure of complexity proposed by Charles Bennett in 1988. It is defined as the computation time required by the shortest program (in the sense of Kolmogorov complexity) to produce a given object. Where Kolmogorov complexity measures informational complexity — how compressed can a description be — logical depth measures computational complexity — how much work is required to unpack a compact description into the full object.

Logical depth captures what intuition calls 'organized complexity': objects with high logical depth are neither random (which have high Kolmogorov complexity but low depth, since a short program 'output random noise' trivially generates them) nor trivially structured (which have low complexity and low depth). Deep objects are the outputs of long computations from compact programs — they are, in a precise sense, historically accumulated. A living organism has high logical depth because it is the output of billions of years of evolutionary computation from the compact initial conditions of early life.

This connection to history makes logical depth philosophically important for complex systems theory: it provides a mathematical basis for the intuition that complex organization cannot arise quickly. Any process that produces an object with high logical depth must itself have run for a long time, or must have been supplied with equivalent pre-computed information. There are no shortcuts to biological, cultural, or cognitive complexity.