Re: What is complexity?

In article <jJIhf.101$HC2.6@trnddc06>,
R. Baldwin <res0k7yx@xxxxxxxxxxxxxxxxxxxx> wrote:
>"Kim G. S. Øyhus" <kim@xxxxxxxxxxx> wrote in message
>news:dm72io$6hs$2@xxxxxxxxxxxxxxxxxxxxx
>> In article <0L2dnVpDOovLaeDeRVn-sw@xxxxxxxxxxx>,
>> dkomo <dkomo871@xxxxxxxxxxx> wrote:
>>>Kim G. S. Øyhus wrote:
>>>>
>>>> That is obviously Dawkings scientific popularizing of Kolmogorov
>>>> complexity.
>>>>
>>>
>>>No it is not. Dawkins is writing about a description of complexity that
>>>has semantic content and is meant to be *understood*.
>>
>> That is still inside of Kolmogorov complexity.
>> And before you argue that it is humans who shall understand, not
>> Turing machines, I hereby preempt this by telling you that humans
>> could also be implemented as programs on a Turing machine, as may
>> the entire universe, with humans.
>
>The Universe is non-deterministic. You would need a non-deterministic Turing
>machine with more resources than the Universe to simulate the Universe. Not
>possible.

Kolmogorov complexity does not depend on the Universe.

And it is perfectly possible to run non-deterministic Turing machines
on a deterministic Turing machine. Do you know how?



>I suspect that humans are also non-deterministic.
>
>>
>>>Frankly, I wish people would stop even mentioning Kolmogorov complexity
>>>as some kind of a metric to consider. Whatever utility this idea has
>>>for AIT, the sad fact is that there is no known method for even
>>>computing the length of the minimal program that will output a given
>>>string, nor to tell if a particular such program is of minimal length.
>>>As a general metric for complexity, Kolmogorov complexity is useless.
>>
>> No, it is not, because it IS possible to give upper bounds on the
>> Kolmogorov complexity. Just take the best description we have so
>> far, and use that as the upper bound.
>>
>
>The upper bound on Kolmogorov complexity for string X is the length of the
>program "print X". If we use this as the estimte for Kolmogorov complexity
>on all strings, nothing is compressed.

You misunderstood me. I was not thinking about the upper bound for the
length of any description, which is far higher than for "print X"
anyway.

I was thinking about the upper bound for the length of possible
shortest descriptions. In other words: An upper bound on the
Kolmogorov complexity.






>>>Dawkins' proposal, on the other hand, is practical and could be put to
>>>immediate use. It doesn't differ that much from the kind of verbal,
>>>mathematical and pictorial descriptions biologists and naturalists have
>>>been writing for hundreds of years now.
>>
>> Neither does Kolmogorov complexity. It incorporates all that stuff as
>> well.
>>
>>
>>
>>>> It is like cryptography, where it is very much easier to describe the
>>>> messages if one have the key than without.
>>>>
>>>> And this is why Kolmogorov complexity assumes infinitely powerful
>>>> machines,
>>>> to avoid the comlexity of missing difficult solutions which are
>>>difficult to find.
>>>>
>>>> Kim0
>>>>
>>>
>>>Maybe so. But my claim is that Kolmogorov complexity is pretty
>>>irrelevant to characterizing real world complexity. Unless you think
>>>the universe is a gigantic computer, the physical laws are algorithms,
>>>and the objects are strings. There are some people who believe that.
>>
>> I am a physicist, and I know the laws we have found do indeed look
>> like algorithms, and the universe does indeed look like it is made of
>> strings.
>
>Are you referring to mathematical strings, or to string theory?

Both.


>> And even if it didn't look like that, AIT would still be valid,
>> because there is no alternative at all.
>>
>
>AIT is a branch of mathematics. It is not all mathematics.

Do you claim to know some part of mathematics which is not
representable somehow on a Turing machine, but which is reperesentable
in Nature?

That is a direct contradiction of the Church-Turing thesis.

Kim0

.

Relevant Pages

  • Re: What is complexity?
    ... >>>machine with more resources than the Universe to simulate the Universe. ... >> Kolmogorov complexity does not depend on the Universe. ... >> And it is perfectly possible to run non-deterministic Turing machines ... The upper bound for Kolmogorov complexity of string X ...
    (talk.origins)
  • Re: Evolutionists Arguing Against The Basis of the ToE
    ... > It seems to me that there is a whole range of text strings that fall ... > way to automate a rule to determine where on that scale any ... the Kolmogorov complexity of the rock is the ...
    (talk.origins)
  • Re: Entropy
    ... Kolmogorov complexity exists in the same sense dragons exist. ... You cannot potentially measure it, or design an algorithm for it, you can only use it as a mathematical abstractum to prove theorems about it. ... You can compute the Kolmogorov complexity for many short strings and a given machine description. ...
    (comp.compression)
  • Re: Characterizing complexity
    ... >> I think that Dawkins is talking about Kolmogorov complexity here. ... >> that the language used to describe the object must be rich enough to ... you have just placed an upper bound on the ... extremely difficult in any rich language. ...
    (sci.bio.evolution)
  • Re: Confused about random strings
    ... of, say, one thousand zero bits generated by some provably stochastic ... regardless of whether that fixed string looks like a "typical" ... You're first comment confuses randomness with Kolmogorov complexity, ... which _is_ a property of fixed strings. ...
    (sci.crypt)