4 ms·
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
by bo1024 13y ago
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.
- Houshalter 13y agoThe website is down so I have no idea what his argument is, but when I studied the concept I found it alarming they just handwave away the issue that it depends what Turing machine you use. There's no reason the constant can't be arbitrarily huge.
- cma 13y agoAs long as arbitrarily huge is finite it doesn't really affect the usefulness of kolmogorov complexity.
- Houshalter 13y agoHow doesn't it? It makes it completely impractical to use because the complexity you get for any string is entirely dependent on the language you use. We have no way of deriving what function set the universe uses from first principles.
- cma 13y agoJust as for any finite string you chose you can chose a finite language L to trivially produce it, for any finite language L you chose, you can chose a finite string S that can't be trivially produced. If you chose L such that it trivially covers the structures of one universe (or a finite number of universes), there are infinite other universes in the same class of complexity which it doesn't cover.
- Houshalter 13y agoI'm not sure if you are disagreeing with me or not. The problem is that we have no idea what language or metalanguage we should start with.
- bo1024 13y agoIf it helps any, the concept of KC is so impractical that this is probably the least of our worries.... The main important thing is that any theorem you prove will hold no matter which programming language/Universal TM you choose.