11–20 of 39 posts
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.
Cool, 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.
This 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.
But those are just formalities, the great beauty of Kolmogorov complexity starts to emerge when you start to consider archive utilities as an approximation for K(x). Think K(x) ~ |Zip(X)| or K(x) ~ |Rar(x)| now you have a real tool to approximate K(x) and guess what it is already installed. Now what about Kd(x,y) = K(x) - K(y)/K(x||y) ~ |Zip(x)| - |Zip(y)| / |Zip(x||y)| It is a distance metric for how entropically far is x from y and that is very interesting and can be very useful for anomaly detection for instance or password strength comparison.
Earlier quoted context omitted.
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.
The author defines language as a mapper from input to output, which is necessary but not sufficient. Its L_silly (written in Ruby) is not a language since it uses "eval" which depends on the entirety of Ruby.
If you really wanted a practical standard measure, the language would have to be simple Turing machine instructions, so that the language implementation isn't more optimized for expressing certain things (which is the problem discussed in the post).
This 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.
|K_1(s) - K_2(s)| This 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.
The major problem with the post is that it does not cover the complexity of the language itself. L(p) should equal to L(d, p) where d is the definition of the language used to write p. So it becomes a whole different question now. And indeed for L(s) where s = (d,p) you can now find the most minimal language definition and an empty p such that it can produce x. K_L(x) = |s| = |d| + |p| And for input receiving program…
It deals with complicated information theory topics similar to Kolmogorov Complexity (albeit by a different name) in an easy-to-approach way. Highly recommended.
[1]: http://www.amazon.com/An-Introduction-Information-Theory-Mat...