# formally defining emergence

From: Ben Goertzel (ben@goertzel.org)
Date: Sun Oct 09 2005 - 07:07:21 MDT

> > Intuitively, H(x) is to be thought of as the complexity of
> producing x, and
> > H(x,y) is to be thought of as the complexity of producing x given y as
> > input. This interpretation makes it plausible to assume that
>
> [BTW: my previous question was dumb: I was assuming you were trying to
> say something a lot more complicated than you really were. Apologies!]
>
> This idea of the "complexity of producing x" now confuses me.
>
> I have too many questions to list.... could you help by just saying what
> this means, and assure me that it does not introduce hidden (i.e.
> implicit)
> assumptions about the possible choices of E, F etc.

I left it vague intentionally but there are a number of precise definitions
that can be plugged in here.

The most basic one would be

H(x) = the length of the shortest self-delimiting computer program that
produces x (running on some fixed, assumed Universal Turing Machine U)

Then we'd also have

H(x,y) = the length of the shortest self-delimiting computer program that
produces x, based on initial input y
(running on some fixed, assumed Universal Turing Machine U)

One elegant way to define the UTM U is to consider it as a classic Turing
machine but with two tapes instead of one. One of the tapes contains
the input y (or is left blank if y=0); the other tape is the standard
data/output tape.

The "self-delimiting" bit is standard in algorithmic information theory
(see Chaitin's book Algorithmic Information Theory) and is necessary to
get the algebra of algorithmic information to work out nicely. See

for the definition. A "self-delimiting code" is the same as a "prefix
code."

There are other variations, for instance, one can modify the definition
of H to take into account program runtime as well as program length,
or the difficulty of finding H via program search ("crypticity"), etc.
But these variations don't make much difference from the perspective
of my email on emergence.

-- Ben

This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:52 MDT