4
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – paul garrett
    Commented Jun 27, 2019 at 21:14
  • $\begingroup$ 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. $\endgroup$
    – Thomas Andrews
    Commented Jun 27, 2019 at 21:21
  • $\begingroup$ The author's intent is precisely to take the size of the algorithm, assumed written with 73 8-bits characters. $\endgroup$
    – user65203
    Commented Jun 27, 2019 at 21:27
  • $\begingroup$ 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. $\endgroup$
    – Thomas Andrews
    Commented Jun 27, 2019 at 21:30
  • $\begingroup$ 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. $\endgroup$
    – rtybase
    Commented Jun 27, 2019 at 21:44

2 Answers 2

Reset to default
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .