Comment by Xcelerate | Hacker News Reader

Comment by Xcelerate | Hacker News Reader

Parent Full thread

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).

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.

Vitanyi 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.

Sounds interesting. Do you have a link to or citation for the paper?

Kolmogorov 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.

The 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.

Well, 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.

Well, 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.

Just wanted to note that we have techniques for termination analysis that cover entire classes of programs of arbitrary length, not just specific short programs. See ranking function synthesis for an example. Hell, under some universal computational models, the halting problem is polynomial-time decidable for almost all programs: https://arxiv.org/abs/math/0504351.

> 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?

No, you can conceive a language which echos everything unless it is prefixed with an operator indicator.

But you still seem to be in agreement that the implementation of the language has a neccesary overhead... printing the operator that indicates code would require another escape sequence, and the overhead of the operator to identify code would mean that some compressible strings dont benefit from compression.

Well of course -- any machine/language is a map from inputs (programs) to outputs, and the pigeon hole principle enforces that if some strings are shortened, others must be lengthened.

Arbitrary 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.

Arbitrary, 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.

The shortest program that outputs "0" is "" (the null program) in the appropriate language, one that just outputs zero.

from 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)

I 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. "

I assumed this was implicit in the article. So perhaps on second though he should have mentioned this more clearly?

Reply on news.ycombinator.com