Re: Characterizing complexity

From: Perplexed in Peoria (jimmenegay_at_sbcglobal.net)
Date: 07/28/04 

Date: Wed, 28 Jul 2004 15:56:27 +0000 (UTC)

"Tim Tyler" <tim@tt1lock.org> wrote in message news:ce7a11$2j68$1@darwin.ediacara.org...
> Perplexed in Peoria <jimmenegay@sbcglobal.net> 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.

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.

Relevant Pages

  • Re: Proof of Uncomputability of Kolmogorov complexity
    ... in particular the proof of why kolmogorov complexity is not computable. ... wondering because your programming language could represent numbers not ... complexity using binary representations too, ... writing a little subroutine that implements binary notation. ...
    (comp.theory)
  • Re: Characterizing complexity
    ... the key point about Kolmogorov complexity is that it insists ... So we have to refer to "length of description in some language" as ...
    (sci.bio.evolution)
  • Re: What is complexity?
    ... >> the entire universe, with humans. ... Kolmogorov complexity does not depend on the Universe. ... and use that as the upper bound. ... >on all strings, nothing is compressed. ...
    (talk.origins)