Any examples of exact calculation 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

There is no universal measure of complexity as it depends on the definition a machine able to decompress the number, as well as on the evaluation rule for the size of the program.

In fact, no attempt has been made to evaluate an exact complexity in a well defined context, because the exact value is quite unimportant. In addition, finding the shortest program is not necessarily an easy task.

Answer 2

See Section 3.2 in Li and Vitanyi, "An Introduction to Kolmogorov Complexity and Its Implementations" (3rd ed), where the authors derive some bounds for Kolmogorov complexity relative to a specific UTM, without omitting arbitrary constants. They also reference some specific constructions by Penrose and Chaitin.