Examples of exact computation of Kolmogorov complexity?

Question

First question: It is known that Kolmogorov Complexity (KC) is not computable (systematically). I would like to know if there are any "real-world" examples-applications where the KC has been computed exactly and not approximately through practical compression algorithms.

Second question and I quote from the "Elements of Information Theory" textbook: "one can say “Print out the first 1,239,875,981,825,931 bits of the square root of e.” Allowing 8 bits per character (ASCII), we see that the above unambiguous 73 symbol program demonstrates that the Kolmogorov complexity of this huge number is no greater than (8)( 73) = 584 bits. The fact that there is a simple algorithm to calculate the square root of e provides the saving in descriptive complexity." Why take the 584 bits as an upper bound for the KC and not include the size of the actual "simple algorithm" that calculates the square root of e?? It is like cheating...

Answer 1

The underlying problem with the example you quote is that it's informal and completely imprecise. As you say, why don't we include the size of the "simple algorithm"? Why are we allowed to assume that it is known what "$e$" is?

Formally, Kolmogorov complexity is defined with respect to a particular encoding of Turing machines. If you fix an encoding, then the Kolmogorov complexity of a string $x$ is $K(x)$, the length of the shortest encoding of a Turing machine that prints that string when started with empty input. (Informally, but still reasonably precisely, you can think of Turing machine encodings as programming languages, and the encoding of a specific Turing machine is a program in that language.)

A key point is that, if we choose different encodings, we get different values for the Kolmogorov complexity. At the level of the informal example, we could both agree that "DO IT!!" means "Print out the first 1,239,875,981,825,931 bits of the square root of e", so now that has very low Kolmogorov complexity. Because of this, it's very unlikely that anyone has sat down and figured out the exact Kolmogorov complexity of some nontrivial string with respect to some specific Turing machine encoding. It would be very difficult to do, and nobody cares about the answer because, in a sense, it's just an artefact of the choice of Turing machine encoding. Unlike actual programming languages, there isn't really any standard scheme of coding Turing machines as strings, so all your hard work would just be proving an uninteresting fact about your arbitrary choice of coding.