- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

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

Date: Thu, 4 Jul 2002 10:03:11 -0700

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

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

*
This archive was generated by hypermail 2.3.0
: Fri Feb 16 2018 - 13:20:07 PST
*