{"id":5912,"date":"2012-02-24T10:30:01","date_gmt":"2012-02-24T17:30:01","guid":{"rendered":"http:\/\/dabacon.org\/pontiff\/?p=5912"},"modified":"2012-02-24T10:30:01","modified_gmt":"2012-02-24T17:30:01","slug":"what-increases-when-a-self-organizing-system-organizes-itself-logical-depth-to-the-rescue","status":"publish","type":"post","link":"https:\/\/dabacon.org\/pontiff\/2012\/02\/24\/what-increases-when-a-self-organizing-system-organizes-itself-logical-depth-to-the-rescue\/","title":{"rendered":"What increases when a self-organizing system organizes itself? Logical depth to the rescue."},"content":{"rendered":"

<\/strong> (An earlier version of this post appeared in the latest newsletter<\/a> of the American Physical Society\u2019s special interest group on Quantum Information.)<\/em>
\nOne of the most grandly pessimistic ideas from the 19th<\/sup> century is that of\u00a0 “heat death” according to which a closed system, or one coupled to a single heat bath at thermal\u00a0 equilibrium,\u00a0 eventually inevitably settles into an uninteresting state devoid of life or macroscopic motion.\u00a0 Conversely, in an idea dating back to Darwin and Spencer<\/a>, nonequilibrium boundary conditions are thought to have caused or allowed the biosphere to self-organize over geological time.\u00a0 Such godless creation, the bright flip side of the godless hell of heat death, nowadays seems to worry creationists more than Darwin\u2019s initially more inflammatory idea that people are descended from apes. They have fought back, using superficially scientific arguments, in their masterful peanut butter video<\/a>.
\n\"Self-organization
\nMuch simpler kinds of complexity generation occur in toy models with well-defined dynamics, such as this one-dimensional reversible cellular automaton.\u00a0 Started from a simple initial condition at the left edge (periodic, but with a symmetry-breaking defect) it generates a deterministic wake-like history of growing size and complexity.\u00a0 (The automaton obeys a second order transition rule, with a site\u2019s future differing from its past iff exactly two of its first and second neighbors in the current time slice, not counting the site itself, are black and the other two are white.)
\n

\"\"
Fig 2.<\/figcaption><\/figure>
\nTime \u2192
\nBut just what is it that increases when a self-organizing system organizes itself?
\nSuch organized complexity is not a thermodynamic potential like entropy or free energy.\u00a0 To see this, consider transitions between a flask of sterile nutrient solution and the bacterial culture it would become if inoculated by a single seed bacterium.\u00a0 Without the seed bacterium, the transition from sterile nutrient to bacterial culture is allowed by the Second Law, but prohibited by a putative \u201cslow growth law\u201d, which prohibits organized complexity from increasing quickly, except with low probability.
\n
\"\"
Fig. 3<\/figcaption><\/figure>
\nThe same example shows that organized complexity is not an extensive quantity like free energy.\u00a0 The free energy of a flask of sterile nutrient would be little altered by adding a single seed bacterium, but its organized complexity must have been greatly increased by this small change.\u00a0 The subsequent growth of many bacteria is accompanied by a macroscopic drop in free energy, but little change in organized complexity.
\nThe relation between universal computer programs and their outputs has long been viewed as a formal analog of the relation between theory and phenomenology in science, with the various programs generating a particular output x<\/em> being analogous to alternative explanations of the phenomenon x<\/em>.\u00a0 This analogy draws its authority from the ability of universal computers to execute all formal deductive processes and their presumed ability to simulate all processes of physical causation.
\nIn algorithmic information theory the Kolmogorov complexity<\/em>, of a bit string x<\/em> as defined as the size in bits of its minimal program<\/em> x<\/em>*, the smallest (and lexicographically first, in case of ties) program causing a standard universal computer U<\/em> to produce exactly x<\/em> as output and then halt.
\n\u00a0x*<\/em> = min{p<\/em>: U<\/em>(p<\/em>)=x<\/em>}
\nBecause of the ability of universal machines to simulate one another, a string\u2019s Kolmogorov complexity is machine-independent up to a machine-dependent additive constant, and similarly is equal to within an additive constant to the string\u2019s algorithmic entropy<\/em> HU<\/sub><\/span><\/em>(x<\/em>), the negative log of the probability that U<\/em> would output exactly x<\/em> and halt if its program were supplied by coin tossing.\u00a0 \u00a0\u00a0Bit strings whose minimal programs are no smaller than the string itself are called incompressible,<\/em> or algorithmically random, <\/em>because they lack internal structure or correlations that would allow them to be specified more concisely than by a verbatim listing. Minimal programs themselves are incompressible to within O<\/em>(1), since otherwise their minimality would be undercut by a still shorter program.\u00a0 By contrast to minimal programs, any program p<\/em> that is significantly compressible is intrinsically implausible<\/em> as an explanation for its output, because it contains internal redundancy that could be removed by deriving it from the more economical hypothesis p<\/em>*.\u00a0 In terms of Occam\u2019s razor, a program that is compressible by s <\/em>bits deprecated as an explanation of its output because it suffers from \u00a0s <\/em>bits worth of ad-hoc assumptions.
\nThough closely related[1]<\/a> to statistical entropy, Kolmogorov complexity itself is not a good measure of organized complexity because it assigns high complexity to typical random strings generated by coin tossing, which intuitively are trivial and unorganized. \u00a0Accordingly many authors have considered modified versions of Kolmogorov complexity\u2014also measured in entropic units like bits\u2014hoping thereby to quantify the nontrivial part of a string\u2019s information content, as opposed to its mere randomness. \u00a0A recent example is Scott Aaronson\u2019s notion of complextropy<\/a>, defined roughly as the number of bits in the smallest program for a universal computer to efficiently generate a probability distribution relative to which x <\/em>\u00a0cannot efficiently be recognized as atypical.
\nHowever, I believe that entropic measures of complexity are generally unsatisfactory for formalizing the kind of complexity found in intuitively complex objects found in nature or gradually produced from simple initial conditions by simple dynamical processes, and that a better approach is to characterize an object\u2019s complexity by the amount of number-crunching (i.e. computation time, measured in machine cycles, or more generally other dynamic computational resources such as time, memory, and parallelism) required to produce the object from a near-minimal-sized description.
\nThis approach, which I have called \u00a0logical depth<\/a>, is motivated by a common feature of intuitively organized objects found in nature: the internal evidence they contain of a nontrivial causal history.\u00a0 If one accepts that an object\u2019s minimal program represents its most plausible explanation, then the minimal program\u2019s run time represents the number of steps in its most plausible history.\u00a0 To make depth stable with respect to small variations in x<\/em> or U<\/em>, it is necessary also to consider programs other than the minimal one, appropriately weighted according to their compressibility, resulting in the following two-parameter definition.<\/p>\n