Depth as a Measure of Natural Complexity ✛ ✎

Original: "Natural Complexity, Computational Complexity and Depth"
· Jon Machta
arXiv:1111.2845 · 2011-11-11 · arXiv non-exclusive · independent analysis · 2 min
Parallel depth measures how many simultaneous steps are needed to assemble a typical state of a system, separating systems with built-in computation from merely correlated ones.

A team assembling a jigsaw puzzle from random pieces: how many simultaneous moves does it take to complete the picture? If the pieces are independent, they all go down at once. If each piece depends on the previous one, you have to work one at a time. So it is with systems: some states assemble instantly, others require a long sequential effort.

The measure proposed by the author is called parallel depth. It is the minimum number of simultaneous steps on an idealized computer with many processors needed to reproduce a typical state of the system. Depth does not ask how much total computation or randomness is involved, only how much parallel time. For a memoryless coin toss, depth is constant: all bits are independent and generated simultaneously. For a coin with memory, depth is logarithmic: the product of independent factors can be computed using a divide-and-conquer approach.

The Santa Fe process has excess entropy growing as a power law T^β, but its depth is also logarithmic: long correlations do not require long computation if they can be parallelized.

Diffusion-limited aggregation (cluster growth by random walk) is a different story. Here each particle must wait for the previous one, and depth grows linearly with the number of particles. Generating such a cluster is P-complete: no fast parallel algorithm exists. Depth is maximal: if a large system contains one small but very complex subsystem, the depth of the whole system is determined by that subsystem, not by averaging over volume.

If an alien researcher measured the complexity of the Solar System by entropy, they would focus on the Sun. But a depth measurement would point to the surface of a small planet, Earth: the biosphere, whose complexity arises from a long evolutionary history.

Previously, it was unclear how to distinguish systems that merely store complex correlations from systems that actually perform long computations. Now it is clear: depth is small for processes with memory, but large for sequential processes like diffusion-limited aggregation. The measure can be applied to classify complex systems in physics, biology, economics, anywhere states are described by probability distributions. The main issue is that depth cannot be computed exactly; it can only be bounded from above by demonstrating increasingly efficient algorithms. But already it helps reveal where genuine computation is hidden within a system.

If an alien researcher measured the complexity of the Solar System by entropy, they would focus on the Sun, where almost all the mass and entropy are concentrated. But a depth measurement would point to the surface of a small planet, Earth: the biosphere, whose complexity arises from a long evolutionary history, not from volume.

Concepts
accuracy complexity computation approximation computational cost entropy computational power chemical composition summation complex systems chemistry volume Natural Language Processing pixel measurement precision quantum measurement classification precision dimension soil moisture