Kolmogorov Complexity - it's a bit silly
forwardscattering.org
Kolmogorov Complexity - it's a bit silly
1–10 of 39 posts
Re: Kolmogorov Complexity - it's a bit silly
#2This seems to be missing the point of Kolmogorov complexity. In Kolmogorov complexity we aren't concerned with the complexity of some fixed finite string, for this very reason.
Re: Kolmogorov Complexity - it's a bit silly
#3This seems to be missing the point of Kolmogorov complexity. In Kolmogorov complexity we aren't concerned with the complexity of some fixed finite string, for this very reason.
If we aren't concerned about the Kolmogorov complexity of any fixed finite strings, then what exactly is it useful for?
Re: Kolmogorov Complexity - it's a bit silly
#4This post is a bit silly. Kolmogorov complexity doesn't have anything to do with computer languages, it has to do with instructions to describe something. The instructions include verysilly, the assembler/interpreter implementation of verysilly, and how to build the computer it's running on.
In that light, the constant factors are still trivial.
Re: Kolmogorov Complexity - it's a bit silly
#5This seems to be missing the point of Kolmogorov complexity. In Kolmogorov complexity we aren't concerned with the complexity of some fixed finite string, for this very reason.
I think the author's point is that K(s) is the shortest program in _any_ language. Thus for any string s there exists a language ("silly,s") that produces the program with length 0 (or 1).
Re: Kolmogorov Complexity - it's a bit silly
#6Cool, thanks. Weird coincidence... just a few days ago I broke out my old information theory textbook (Cover & Thomas) and worked through this exact same line of reasoning to convince myself that "the Kolmogorov complexity" of a string depends very strongly on the choice of language, and can be brought down to 0 in adversarial cases like what you described.
Re: Kolmogorov Complexity - it's a bit silly
#7This post is a bit silly. Kolmogorov complexity doesn't have anything to do with computer languages, it has to do with instructions to describe something. The instructions include verysilly, the assembler/interpreter implementation of verysilly, and how to build the computer it's running on. In that light, the constant factors are still trivial.
If you want to define KC as the minimal length of some set of instructions to describe the string, then you still haven't gotten away from the fact that a common language must still be fixed in advance. You just changed it from a computer language to English (or whatever language your instructions are written in).
Re: Kolmogorov Complexity - it's a bit silly
#8This seems to be missing the point of Kolmogorov complexity. In Kolmogorov complexity we aren't concerned with the complexity of some fixed finite string, for this very reason.
I think the author's point is that K(s) is the shortest program in _any_ language. Thus for any string s there exists a language ("silly,s") that produces the program with length 0 (or 1).
But this just misunderstands the definition. In the standard definition you pick _some_ Turing-complete language, and then define K(s) with respect to that language. You can then go on to show that in the limit of longer and longer strings, it does not make much difference which language you pick.
Re: Kolmogorov Complexity - it's a bit silly
#9This seems to be missing the point of Kolmogorov complexity. In Kolmogorov complexity we aren't concerned with the complexity of some fixed finite string, for this very reason.
If we aren't concerned about the Kolmogorov complexity of any fixed finite strings, then what exactly is it useful for?
It's a mathematical device for reasoning about compressibility. It's like saying "What's the use of Shannon Entropy of fixed strings?"
Algorithmic information theory also allows you to re-derive Godel's Incompleteness Theorem or the Halting Theorem from it, in a sense, it's a super-set of those concepts.
For example, we can talk about the compression of knowledge into finite sets of axioms and many bits of information exist in such a system.
Or we can reason about concepts like Omega, a truly random number in mathematics, incompressible in the sense then there is provably no shorter way to encode it other than brute force calculating it, but which is a real number, and which we can know the first few bits of it. (and a quite interesting number in the sense that it's an Oracle of knowledge and if you had it's complete expansion, you could solve many questions in mathematics with it)
Re: Kolmogorov Complexity - it's a bit silly
#10Earlier quoted context omitted.
If we aren't concerned about the Kolmogorov complexity of any fixed finite strings, then what exactly is it useful for?
It's a mathematical device for reasoning about compressibility. It's like saying "What's the use of Shannon Entropy of fixed strings?" Algorithmic information theory also allows you to re-derive Godel's Incompleteness Theorem or the Halting Theorem from it, in a sense, it's a super-set of those concepts. For example, we can talk about the compression of knowledge into finite sets of axioms and many bits of informatio…
Interesting. Is this the Omega you're referring to?