Perplexed in Peoria  wrote or quoted:
> "Tim Tyler"  wrote in message
news:ce7a11$2j68$1{at}darwin.ediacara.org...
> > Perplexed in Peoria  wrote or quoted:

> > > I think that Dawkins is talking about Kolmogorov complexity here.  To
> > > my mind, the key point about Kolmogorov complexity is that it insists
> > > that the language used to describe the object must be rich enough to
> > > say things like "repeat N times" and more
complicated variations of that
> > > phrase. [...]
> >
> > So we have to refer to "length of description in some
language" as
> > something like "generalised Kolmogorov complexity" -
while "Kolmogorov
> > complexity" refers to only "length of description in some Turing-
> > complete language"?
> >
> > If so, that has the blahs :-(
> 
> The real problem with Kolmogorov is that complexity is defined as the
> length of the _minimum_ length description available in the language.
> And, it almost has to include that "minimum" in its
definition.  But that
> means that, for all practical purposes, you can never be sure that the
> description you are using to make your measurement is the minimum length
> one.

Since the problem of finding a maximally compressed represntation 
of something is as hard as the Halting problem, i.e. there's no way
to do it in the general case.

> But I don't think that fixing the definition on some particular Turing-
> complete language is a serious limitation.  No other reasonably rich language
> is likely to be much more efficient.  So, if you provide a compact description
> in your favorite language, you have just placed an upper bound on the
> Kolmogorov complexity.  And placing a lower bound on the complexity is
> extremely difficult in any rich language.

It depends on the Turing-complete language language you pick to 
standardise on.  If all programs in that language are defined to
start with a header of 10Mb of "{at}" symbols - then the resulting
program lengths won't have much to do with what people commonly
refer to as complexity.

There's an argument that it's not lengths of *programs* that should
be compared - since programming languages are far too arbitrary.

What you *really* need to compare is the size of the machine
that does the calculation - since that necessarily includes the 
interpreter for any programming language you choose.

Then the programming language is no longer an arbirary variable, since
the virtual machine the program runs of has already been chosen by 
nature - it's one based on the laws of physics.

Of course, this approach has some drawbacks of its own ;-)
-- 
__________
 |im |yler  http://timtyler.org/  tim{at}tt1lock.org  Remove lock to reply.
---
þ RIMEGate(tm)/RGXPost V1.14 at BBSWORLD * Info{at}bbsworld.com

---
 * RIMEGate(tm)V10.2áÿ* RelayNet(tm) NNTP Gateway * MoonDog BBS
 * RgateImp.MoonDog.BBS at 7/29/04 12:58:44 PM