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
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
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:52 MDT