3
$\begingroup$

Kolmogorov complexity is relative to a choice of Universal Turing Machine. Because of the Invariance Theorem, the difference in complexity assigned by two Universal Turing Machines is bounded by a constant that depends on the choice of that pair. They can't disagree too much because one can always switch over to emulating the other. However, this amount of maximum disagreement can be arbitrarily large.

Given that, of what use is Kolmogorov complexity? I suppose if you have a sequence of bitstrings, then you can talk about the asymptotic growth of the complexity of these bitstrings, and you will know that this is independent of choice of UTM.

But I thought that Kolmogorov was supposed to be meaningful for individual finite strings. But every bitstring can be produced by an arbitrarily small program: imagine a language that functions just like Java but where an empty file produces the bitstring under consideration.

Doesn't this relativity make Kolmogorov complexity basically pointless? I must be mistaken, right?

$\endgroup$
  • $\begingroup$ There is a slight refinement here. Not all bit strings are produced by small programs. Your question and this comment wasn't. $\endgroup$ – Paul Uszak Nov 24 '17 at 3:11
2
$\begingroup$

The relativity is up to an additive constant. Suppose that you express Kolmogorov complexity relative to your favourite universal Turing machine $U$, but I do it relative to my favourite UTM $V$. If the shortest program for $V$ that outputs a string $x$ is $M$, then the shortest program for your machine $U$ can't be any longer than the one that simulates $V$ running $M$, and that has length $|M|+k$, where $k$ is the size of the simulator.

So, yes, you could pick a UTM that has a very efficient coding for some finite set of strings. However, that would increase the length of the coding of at least that the same number of other strings, and we're typically interested in the asymptotic behaviour of infinite families of strings, rather than individual strings.

$\endgroup$
  • $\begingroup$ Thanks for your answer! I understand how Kolmogorov complexity is useful for infinite families. However, I don't understand its utility for individual or a finite number of bitstrings. It feels like your prior belief on what machines are likely could easily be the greatest factor in how complex these bitstrings look to you. $\endgroup$ – Ned Ruggeri Oct 17 '17 at 21:43
  • $\begingroup$ I do not think that your second paragraph is true. It seems like a description of general compressor which is not the point of KC for finite strings, but the consequence. It describes the application of compressor for fixed values outside domain of inputs. $\endgroup$ – Evil Oct 18 '17 at 3:48
  • $\begingroup$ @NedRuggeri Can you give an example of Kolmogorov complexity being used to argue about finite collections of strings? $\endgroup$ – David Richerby Oct 18 '17 at 7:29
  • $\begingroup$ @Evil OK, maybe not all other strings, but at least as many as you shortened must lengthen. $\endgroup$ – David Richerby Oct 18 '17 at 7:31
  • $\begingroup$ arxiv.org/pdf/math/0110086.pdf and maybe paper from Lempel and Ziv from 1976 (researchgate.net/publication/…). $\endgroup$ – Evil Oct 18 '17 at 8:02
0
$\begingroup$

I think the key point that is missing is that task for infinite families of bitstrings is not that different from fixed bitstrings.

The Kolmogorov Complexity measures the length of your Java code or any other language, it may also measure the compiled program length, which is still relative to architecture and OS. When you imagine a program taking input then you are probably thinking about conditional Kolmogorov Complexity.
The standard KC states that it is the length of a program in predetermined description, it is true that various languages, hardware and software will yield various result, but we are interested in particular configuration to find the minimal description. Taking it to any level, the minimal amount of information needed is the same. The constant that occurs due to invariance theorem is irrelevant for many theoretical aspects, and takes into account the UTM choice, which allows to concentrate on the main problem: how compressible is given bitstring and move on.

For finite amount of bitstrings we are interested in the sum of one programs length and inputs lengths that will recover the original representation, but such program will not be able to produce anything else. Good, it was not the point!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.