Logical depth

From: Tim May <tcmay.domain.name.hidden>
Date: Thu, 4 Jul 2002 10:03:11 -0700

On Thursday, July 4, 2002, at 09:26 AM, Hal Finney wrote:

> Brent Meeker writes:
>> What's Wolfram's critereon for "randomness"? how it looks? It would
>> seem
>> that he's using something different than Chaitin if we thinks a simple
>> system can produce random output. Chaitin *defines* random as an
>> output
>> that can't be reproduced by a system simpler than the output itself.
>
> That's a good point. It's curious that Chaitin used the primes as an
> example of mathematical randomness when they must have inherently low
> algorithmic complexity. A handful of relatively short axioms define the
> integers and the operations of addition, multiplication, etc., and this
> is sufficient to produce the "random" spacing of the primes.

However, the "dual" of "descriptional complexity" is "logical depth":
the running time of a program to generate some string or set from some
initial conditions or axioms. An apparently complex system, one which
apparently has no description shorter than itself, may arise from a
short description run through a machine or process a number of times.
Logical depth is the term coined by Charles Bennett, of course.

(Arguably, the universe is such a high logical depth system.)

I say "apparently complex" rather than "complex" to admit this very
possibility: that an object with seemingly no shorter description of
itself _than_ itself ("random" in Kolmogorov-Chaitin sense) actually has
a much shorter description.

Examples of this abound. An apparently random string may be a very
simple string run through an encryption process. An apparently random
string may have a very short description once someone spots the pattern.

A DNA string coding for some organism which has evolved over billions of
generations has "packed" a lot into a fixed length string. Each
twiddling of the string through mutation and crossover, followed by each
test of reproductive fitness, is effectively a computation. The "spring"
of this string is "compressed" with more and more energy. The DNA string
for an organism has a lot of "energy" or "cleverness" (viewed in
different ways). The string length remains the same, more or less, and
naive calculations of entropy (which are always simplistic) give
essentially the same measure. But the logical depth is different, and
that matters a lot.

We can say "the set of primes is not random, but has high logical
depth." It will take a certain amount of energy to generate/compute the
primes up to some number.

I think Chaitin is making a point about the set of primes being a
readily-visualizable example of something which has a seemingly random
structure but with high logical depth. Which is what a lot of cellular
automata, e.g., LIFE, have been showing us.

Simple initial conditions + Long running times ---> Complex structures
with no simpler descriptions than themselves

(unless we know the initial conditions and algorithms, in which case we
can do the computation ourselves)

Aside: Trying to compute the initial conditions from a final
configuration is difficult. This was dealt with in some of Wolfram's
earlier papers, collected together in his World Scientific book
"Cellular Automata."


--Tim May
"Stupidity is not a sin, the victim can't help being stupid. But
stupidity is the only universal crime; the sentence is death, there is
no appeal, and execution is carried out automatically and without pity."
--Robert A. Heinlein
Received on Thu Jul 04 2002 - 10:10:00 PDT