**From:** Ben Goertzel (*ben@goertzel.org*)

**Date:** Sun Oct 09 2005 - 07:07:21 MDT

**Next message:**Ben Goertzel: "RE: Emergence"**Previous message:**rpwl@lightlink.com: "(no subject)"**In reply to:**rpwl@lightlink.com: "(no subject)"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

*> > 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

http://www.talkorigins.org/faqs/information/algorithmic.html#selfdel

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

**Next message:**Ben Goertzel: "RE: Emergence"**Previous message:**rpwl@lightlink.com: "(no subject)"**In reply to:**rpwl@lightlink.com: "(no subject)"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

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