# Any examples of exact calculation of Kolmogorov Complexity??

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

• Kolmogorov (-Solomonoff-Chaitin) complexity is only determined relative to some context, as you observe... So it starts to make more sense looking at asymptotics of several closely related problems, rather than a single computation. – paul garrett Jun 27 '19 at 21:14
• Yeah, using English, or any human language, this way in discussing KC is not a good approach. You can imagine a computer language/context where this is enough information to get the program to compute the bits, but it will likely not be English. Treat that as only a motivational example, not a rigorous statement. – Thomas Andrews Jun 27 '19 at 21:21
• The author's intent is precisely to take the size of the algorithm, assumed written with 73 8-bits characters. – Yves Daoust Jun 27 '19 at 21:27
• A very simple programming language would just have one statement, "write(c)" where c is one of the possible letters. Then for any string $s$ the only program to output the string is a sequence of $n$ statements, one per character, so the KC is $\Theta(len(s)).$ You can come up with the exact shortest length of the program, depending on how the language applies. We usually only care about $\Theta(\cdot)$ of KC. – Thomas Andrews Jun 27 '19 at 21:30
• For the 1st question: yes, for example "010101010101010101010101...01...", but KC depends on the Turing machine of your choice. It's quite likely you will get different answers from (e.g.) Java and Python programmers. – rtybase Jun 27 '19 at 21:44