5 ms·
While what the author says is true (and I'm sure he knows vastly more about the subject than I do), I think the way that Kolmogorov complexity is described in t
by Xcelerate 8y ago
While what the author says is true (and I'm sure he knows vastly more about the subject than I do), I think the way that Kolmogorov complexity is described in the article is a bit misleading to a general audience. For short strings, we often can and do compute the Kolmogorov complexity. See some of Hector Zenil's work, e.g. "Calculating Kolmogorov Complexity from the Output Frequency Distributions of Small Turing Machines" (https://arxiv.org/abs/1211.1302 https://arxiv.org/abs/1211.1302).
What "uncomputable" means is that for the general case, there cannot exist a program that is guaranteed to find the Kolmogorov complexity of a given input string. This is because as we enumerate through all Turing machines from smallest to largest, some will not halt, but we can’t know if this is because the program is just running for a very long time or if it is actually going to run forever. In specific cases for short strings, we can often analytically determine whether the program will halt or not. This is also why we know the first few values of the Busy Beaver function, even though it is also uncomputable.
- mikorym 8y agoI assumed this was implicit in the article. So perhaps on second though he should have mentioned this more clearly?
- mirceal 8y agofrom the article, to me it seems pretty clear that the message is "finding the complexity for the general case is impossible" (ie for certain, short, strings we can definitely figure it out)
- xamuel 8y agoKolmogorov Complexity is not a single explicitly-defined function: it depends on your model of computation. For large strings, this doesn't matter very much, because if you have a program of length n in one Turing complete programming language L1, it only takes O(1) extra code to transform your program into a program in another Turing complete programming language L2 that does the same thing. However, for small strings, the actual complexity you compute starting from any particular model of computation is totally dwarfed by that O(1) padding cost. So, actually computing Kolmogorov complexities of small strings is basically just pointless trivia.
- Xcelerate 8y agoThe O(1) "language" term is discussed in the linked article. The authors use Levin’s semi-measure, which constitutes the Universal Distribution, in combination with the Coding Theorem to approximate a KC that is independent of any specific Turing machine.
- 29galoseats 8y agoVitanyi and colleagues have a paper where they show that although K(X) is uncomputable, in practice, you can attach a probability to one X having greater or lesser K(X) than another X (to ridiculously oversimplify; K(X|M) might be better notation). This is kind of analogous to p-values and is related to the statistical interpretations of Kolmogorov complexity. The uncomputability is important but is not the intractable obstacle it seems like if not elaborated on.
- btrettel 8y agoSounds interesting. Do you have a link to or citation for the paper?
- jeromebaek 8y agoWell, obviously, the shortest program that outputs "0" is "0". And the shortest program that outputs "1" is "1". We're only interested in the general case, not specific cases. Sometimes I think this distinction between "general" and "specific" is as deep as the whole idea of uncomputability. When someone says "arbitrary Turing machine" it is very difficult for a layman to wrap their head around what this means. No wonder: I'm using the word "arbitrary", which means "random", which means... uncomputable.
- enkid 8y agoArbitrary doesn't mean random. It means chosen randomly, as in any Turing Machine chosen randomly will work in that situation. The output isn't random, the output for one Turing Machine should be the same for all Turing Machines.
- smadge 8y agoArbitrary, when used in mathematics, also does not mean chosen randomly. It is used as a synonym for “any” or “every.” Furthermore, it doesn’t really make sense to speak of “choosing randomly” from a set without specifying a probability distribution. Often times it is implicit that someone is talking about a uniform distribution, but since the set of all Turin machines is infinite, it can’t have a uniform distribution.
- sadgit 8y ago> the shortest program that outputs "0" is "0". Im tempted to debate this... in any programming language you need to use some space to differentiate a literal from code to be executed. So, according to Kolmogorov complexity, wouldn’t the shortest program to print a random number (or 0) be larger than that number?
- nl 8y agoNo, you can conceive a language which echos everything unless it is prefixed with an operator indicator.
- alimw 8y agoI agree. Surely these sentences are outright wrong: "While a computer might find some pattern in a string, it cannot find the best pattern. We might find some short program that outputs a certain pattern, but there could exist an even shorter program. "