Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Kolmogorov Complexity - it's a bit silly

forwardscattering.org

Post reply on HN
Print view View original

21–30 of 39 posts

Re: Kolmogorov Complexity - it's a bit silly

#21

Post by azakai »

The point is entertaining, but does not undermine Kolmogorov complexity.

First, for any single fixed language, the problem does not exist. That includes any single L_silly language.

Second, when considering the set of all languages, there is indeed an issue. However it can be remedied by requiring an implementation of the language - while we might say that program P_117 has, in language L, the semantics that it emits

2983483746923874560238475613849523984560238475620837456198736491378461938764134

(a fixed very long string), supposedly showing that P_117 which is of length 5 can emit such a long string, it doesn't really. To implement that language, you would need to encode that long string somehow in the implementation.

In other words, if you consider a single language, that's fine. If you consider all possible languages, you must require an implementation of them, not just an abstract definition. The implementation must be shared between all of them, which is equivalent to a single language in the first place. And a single language is really where the benefit and intuition of Kolmogorov complexity lies anyhow.

The confusion arises when we try to prove that the language "doesn't matter" as it's just a constant factor. There is something faulty with that proof, or rather it proves something other than what it is assumed to, but Kolmogorov complexity itself is still valid.

Re: Kolmogorov Complexity - it's a bit silly

#22

Post by codeflo »

An analogy: there are multiple calendar systems in widespread use. Each one of those defines a different year 0. In fact, how I define time 0 is completely arbitrary, so that for any given moment in time, I can define a calendar system that defines this moment to be exactly 00:00:00 on day 1 of year 0 in my new calendar system. From this fact, using the logic of the article, I can show that any moment is time 0 (in some calendar), and thus measuring time is completely pointless!

Re: Kolmogorov Complexity - it's a bit silly

#23

Post by javajosh »

If you allow your definition of "language" to include those that output the same fixed string for any input, then yes, much silliness will ensue. But of course, this has nothing to do with Kolmogorov, and everything to do with the fact that you often get silliness when you redefine words into meaninglessness.

Re: Kolmogorov Complexity - it's a bit silly

#24

Post by codeflo »

azakai wrote: post #21

The point is entertaining, but does not undermine Kolmogorov complexity. First, for any single fixed language, the problem does not exist. That includes any single L_silly language. Second, when considering the set of all languages, there is indeed an issue. However it can be remedied by requiring an implementation of the language - while we might say that program P_117 has, in language L, the semantics that it emits…

> There is something faulty with that proof, or rather it proves something other than what it is assumed to, but Kolmogorov complexity itself is still valid.

Well, Kolmogorov complexity depends on language choice, there's no way around that and the invariance theorem doesn't say anything different. It's more subtle than that, so we have to be precise.

The invariance theorem shows that given languages L and M, there's a constant c such that for any string x, |K_L(x) - K_M(x)| plus .

What this means is that given sufficiently large and complex strings x, K_L(x) is very close to K_M(x), because c is constant and finite, while you can construct a string x with arbitrarily large K_L(x). This gives us confidence that K_L measures something "real", even though our measurement is relative to the (arbitrary) definition of L.

Of course, for short programs, the constant factors dominate. You won't get a shorter Ruby program for your 30 character string by implementing a full Perl interpreter. In this case, the constant difference c is so large relative to |x| that the invariance theorem, while technically correct, is basically pointless.

Re: Kolmogorov Complexity - it's a bit silly

#25

Post by thro2 »

This proof doesn't show that Kolmogorov complexity of any fixed string is 0, it shows that Kolmogorov complexity of any fixed string is constant (which is trivial). That is obscured by an abuse of notation which makes arguments about Kolmogorov complexity easier to parse in 99% of cases. So, imho, this post isn't very substantial - it's essentially a garden variety "1 = 2" sort of argument.

Re: Kolmogorov Complexity - it's a bit silly

#26

Post by azakai »

codeflo wrote: post #24
azakai wrote: post #21

The point is entertaining, but does not undermine Kolmogorov complexity. First, for any single fixed language, the problem does not exist. That includes any single L_silly language. Second, when considering the set of all languages, there is indeed an issue. However it can be remedied by requiring an implementation of the language - while we might say that program P_117 has, in language L, the semantics that it emits…

> There is something faulty with that proof, or rather it proves something other than what it is assumed to, but Kolmogorov complexity itself is still valid. Well, Kolmogorov complexity depends on language choice, there's no way around that and the invariance theorem doesn't say anything different. It's more subtle than that, so we have to be precise. The invariance theorem shows that given languages L and M, there's…

Yes, exactly. I think the difficulty is that the invariance theorem talks about any two fixed languages - then we can bound the difference between them - but the article here talks about all possible languages. If you consider them all at once, things do seem peculiar, but it's meaningless: Considering any one is sufficient, and the invariance theorem justifies that by showing that no other one would be better.

Re: Kolmogorov Complexity - it's a bit silly

#27

Post by tromp »

mappum wrote: post #15

The author misses the point that Kolmogorov Complexity isn't meant to be used as a practical measurement, but is just a theoretical way to think about information. There is no way to measure a string's "Kolmogorov Units", but you can just generally agree that "abababababababababababababababababababab" is less complex than "ababaaabbabaabaababbbabaababbbaaababbbba". If you really wanted a practical standard measure, t…

Basing a concrete definition of Kolmogorov complexity on the lambda calculus rather than Turing machines has many advantages.

See https://en.wikipedia.org/wiki/Binary_lambda_calculus for a concrete definition, and a proof that the complexity of the prime numbers is at most 167 bits.

This language can be implemented in only 25 lines of C.

Re: Kolmogorov Complexity - it's a bit silly

#28

Post by bo1024 »

The post has an incorrect definition of Kolmogorov Complexity.

It says:

> The overall Kolmogorov complexity of a string is thus defined as K(x)=|p| where p is the shortest program string for language L such that L(p)=x and we consider all programming languages.

This is wrong. The definition of Kolmogorov complexity is always given relative to some fixed programming language. For example, K_perl or K_ruby are just fine, although we usually consider some Universal Turing Machine. The reason that we can prove theorems about Kolmogorov Complexity without even specifying which language we fixed is because of invariance (on all but a finite number of strings, any two languages will differ by at most some fixed constant). But the point is that you have to take a single fixed programming language. Then the issue raised in the blog post does not arise.

As this post is almost a year old, I doubt it matters much or is worth contacting the author though. But for future reference, if you think you've found such a basic mistake in a foundational concept in math or CS, you can always ask about it on cs.stackexchange.com or math.stackexchange.com rather than making a potentially embarassing post about how mathematicians are wrong/silly.

Re: Kolmogorov Complexity - it's a bit silly

#30

Post by darkmighty »

TrainedMonkey wrote: post #11

----- PS C:\programming\Kolmogorov> ruby .\interpreter.rb "puts(\`"ab\`" * 20)" abababababababababababababababababababab So even with this universal language, we still have Ksilly,x2(x2)=0 ----- So you input string "puts(\`"ab\`" * 20)" into a ruby program, and somehow Kolmogorov complexity is 0 and not length of the argument you passed? I don't buy that.

Yea, he's wrong on that. The point of tailoring languages to a string still -- weakly -- stands, though: but he could also do that for a finite number of strings. Weakly also because he completely misses the point of Kolmogorov complexity. It's not meant to be practical in any way. It's a mathematical tool to uncover some facts about the complexity of things (mostly mathematical objects) and a more solid framework for data compression and randomness, which he glanced at the beginning of the article. In a sense it's like other non-computable constructions, it provides truths without specific instances, because their existence would be too powerful.

Some of the interesting theorems are found in a chapter of the following book:

http://www.amazon.com/Elements-Information-Theory-Thomas-Cov...

It gives a good grasp that Kolmogorov complexity answers meaningful questions not well defined in regular information theory: questions of optimality in finite lengths.

Post reply on HN