The weblog of Nicholas Chapman Kolmogorov Complexity - it's a bit sillyPosted 25 Jun 2013 Kolmogorov Complexity is kind of a cool idea, at least at first glance. You may know that the information content of an infinite stream of random symbols (measured in bits per symbol) is given by the entropy as described by Claude Shannon. The entropy is all well and good, but it would be nice to have a measure for the information content in a finite length string. Kolmogorov Complexity gives a nice description of the information content of a finite string by how much information it takes to describe the string. Take the two strings: $$abababababababababababababababababababab$$ $$ababaaabbabaabaababbbabaababbbaaababbbba$$ The first string can be described as 'ab repeated 20 times'. The second string, since it is more-or-less random, can't be described in a simpler way than just reciting the whole string. Kolmogorov Complexity says that the first string has a lower complexity, or information content, relative to the second string. A little more formally, suppose we have some programming language L. (For example, L could be Ruby) L takes as input program strings p, that when run by the language L, produce an output string $$L(p)$$ (if the program halts). Take a string x. x could be the output of many different programs p. However, there will be one (or more) programs that are shorter than any other programs that produce x. The length of such a p (call it |p|), is the Kolmogorov complexity of x. The Kolmogorov complexity of a string, for some language L, is thus defined to be $$K_L(x) = |p|$$ where p is the shortest program string such that $$L(p) = x$$ Let's do some examples with L = Ruby. Take the string x_1 = $$abababababababababababababababababababab$$ that we saw above. This can be output with the ruby program puts "ab"*20  This program is 11 bytes long. Let's work in bytes for now, since it's not really possible to have non-byte length programs. So for this program, call it p_1, $$|p_1| = 11$$ There may be a shorter program that can spit out the string x above (Maybe some Ruby experts will know one). However, we do at least have an upper bound on the Kolmogorov complexity of x_1 for the ruby language: $$K_{ruby}(x_1) <= 11$$ Now let's consider the other string, x_2 = $$ababaaabbabaabaababbbabaababbbaaababbbba$$ The shortest program that will spit this out (that I know of) is puts"ababaaabbabaabaababbbabaababbbaaababbbba"  Which is 46 bytes long. So we know $$K_{ruby}(x_2) <= 46$$ If we accept that these upper bounds are reasonably tight (which I think is reasonable), then we can conclude that the first string has a much lower Kolmogorov complexity than the second, as we said earlier. At this point, you may reasonably ask, 'but what about other languages such as C++ or Perl?' Obviously since C++ is so verbose, you are not going to do better in terseness than Ruby. But what about 'line-noise as syntax' Perl? It's entirely possible that $$K_{perl}(x_1) < K_{ruby}(x_1)$$ In general the Kolmogorov complexity of a particular string is going to vary with the programming language L. Isn't this a problem? Wikipedia will tell you something like "The length of the shortest description will depend on the choice of description language; but the effect of changing languages is bounded (a result called the invariance theorem)." The effect of changing languages is bounded because the first language can interpret the second, and vice-versa (assuming the languages are universal). For example, if we had a nice Perl program that spits out a string, we could write a Perl interpreter in Ruby, concatenated with the original Perl program. The length of the Perl program is the constant described above. 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. At this point, people seem to think the problem solved. There's just one little hitch. When dealing with finite length strings, constant factors are important, especially when they can be much longer than the strings in question. Anyway, to show why Kolmogorov complexity is a bit silly, I will define a class of new programming languages $$L_{verysilly,i}$$ such that $$L_{verysilly,i}$$ is puts i  In other words, all the programming language does is discard any program input and print out the string i. So, let's have another look at the Kolmogorov complexity of $$x_2 = ababaaabbabaabaababbbabaababbbaaababbbba$$ Given that if we feed the empty program string into it we get x_2: $$L_{verysilly,x_2}('') = x_2$$ Then the shortest program that produces x_2 is obviously the empty string '', which has length zero, so $$K_{verysilly,x_2}(x_2) = 0$$ In general, for any (finite) string x, there exists some very silly language $$L_{verysilly,x}$$ such that it spits out x: $$L_{verysilly,x}('') = x$$ and so the Kolmogorov complexity of x is zero in this language. $$K_{verysilly,x}(x) = 0$$ Perhaps you might protest that such very silly languages aren't 'proper' programming languages like Ruby, since they ignore the program string completely, and can only produce one output. And that would be quite reasonable. Let us restrict ourselves to universal languages then (e.g. languages that can simulate any other programming language / Turing machine) We can introduce the slightly less silly language class $$L_{silly,i}$$ Where $$L_{silly,i}$$ is defined as the programming language (implemented in Ruby): arg = ARGV[0] if(arg.nil?) puts i else eval(arg) end  What this does, is if the input string is empty (I'm checking for Null here as Ruby or Windows seem to confuse the empty string with the null string), then it prints out the string i and terminates. Otherwise it evaluates/executes the string as a Ruby program. To take a concrete example, the language $$L_{silly,x_2}$$ is arg = ARGV[0] if(arg.nil?) puts "ababaaabbabaabaababbbabaababbbaaababbbba" else eval(arg) end  If you pass the empty string to this language, it prints out the x_2: PS C:\programming\Kolmogorov> ruby .\interpreter.rb "" ababaaabbabaabaababbbabaababbbaaababbbba  However it can also evaluate arbitrarily complex programs: PS C:\programming\Kolmogorov> ruby .\interpreter.rb "puts(\"ab\" * 20)" abababababababababababababababababababab  So even with this universal language, we still have $$K_{silly,x_2}(x_2) = 0$$ So to go over what we have constructed: Theorem: The Kolgomorov complexity of all (finite) strings is zero. Proof: Take any string i Consider the language $$L_{silly, i}$$ Where $$L_{silly, i}('') = i$$ (The empty string case) and $$L_{silly, i}(x) = L_{ruby}(x)$$ if x is not the empty string. Since $$|''| = 0$$ therefore $$K_{silly, i}(i) = 0$$ and therefore $$K(i) = 0$$ q.e.d. So Kolmogorov complexity as it's currently defined has restricted utility. Maybe if you restrict the language to just a single language then it is useful. But if you allow any language to be used you run into the silly situation described above. Maybe there's some variation on Kolmogorov complexity out there that avoids the dependence on a particular language, while still capturing the neat idea at the heart of it. Do you have a comment or feedback about this blog post? Please email me.< Back All content by Nicholas Chapman. Static Pages on this website Our software Indigo Renderer Chaotica Substrata Winter