Re: Entropy

Mok-Kong Shen wrote:

OK. Let me aks your favour to do one thing: In all the books
I have looked at, Komolgorov complexity is defined for finite
strings and no where is any inappropriateness of finite
input mentioned.

None of the above stuff is new, it's just conclusions from the obvious. While I generally don't appreciate Wikipedia for things like this, just go there. You'll find there exactly the same elementary result I stated above, namely that the complexity is language dependent, and that for any two languages the complexity of a given string differs by a constant (depending on the languages). The specific "lena" example is this invariance theorem, just turned around. By making the machine pretty smart, one can make the constant c as large as the language, and then the complexity of *a specific* string very short.

For any *finite* string the complexity isn't a function of the input string itself. However, if you approach the limit of longer and longer strings, this constant becomes irrelevant, but only then.

There is no big science behind that, really.

So your claim that for finite input Komolgorov
complexity makes little sense must be something new in the
field. Could you please give a reference to a book or a journal
that supports your claim, or is it a yet unpublished scientific
result of your own?

Definitely not.

For example, go into Ray Solomonoff's work "A Preliminary Report on a General Theory of Inductive Inference," Report V-131, Zator Co., Cambridge, Ma. Feb 4, 1960." cited there. Go to section 4, and read it. It states exactly what I say - the constant in the above equation becomes irrelevant for long strings, and only then - and *then* the definition is machine-independent. Otherwise, it depends on the machine, clearly. That I can set the complexity to one for a *specific* message is a trivial corollary from the invariance theorem. Specific means here:

For any message A there exists a Turing machine U such that C_U(A) = 1.

quite contrary to:

There is a Turing machine U such that for any message A C_U(A) = 1.

which is a different statement, and clearly wrong. As I might have said already, it depends on the position of the quantors. As the description of a Turing machine is by definition finite, the second statement is clearly wrong since I can always set the message just considerably longer than the description of the machine to be on the safe side. This does not hold for the first statement.

Really, it's just about reading the statement carefully.

So long,
Thomas
.

Relevant Pages

  • Re: =?iso-8859-1?q?Re:_Kolmorgorov_Complexity_and_Kim_=D8yhus?=
    ... >>>As far as Kolmogorov Complexity, let's look at the basic definition one ... When discussion a string of characters. ... >>>the degree of a string's compressibility. ... >>>plays an important role in the concept of chaos. ...
    (talk.origins)
  • Re: Complexity; was: SQL
    ... > strings when we don't know the language. ... Though in software developing complexity is not lengths. ... then the sequence is not random. ... > Computable string is not random. ...
    (comp.object)
  • Re: Just for fun...
    ... complexity in practical scenarios... ... corresponding complexities for a given string can differ at most by a constant ... When I first learned about the concept of compression, ... surprise in the questions/issues being discussed, ...
    (comp.lang.ruby)
  • Re: Problem with a problem
    ... language. ... The word problem isn't in P there. ... pretty much any complexity problem and they all seem to be of the form ... find a clique on input of a string describing a graph, ...
    (comp.theory)
  • Re: Entropy
    ... You'll find there exactly the same elementary result I stated above, namely that the complexity is language dependent, and that for any two languages the complexity of a given string differs by a constant. ... In the Wiki page there is no mention of "infinite string". ... Kolmogorov complexity but unfortunately failed. ...
    (comp.compression)