0
$\begingroup$

Is the Kolmogorov complexity of any piece of information with respect to a certain predefined encoding for all pieces of information, or can the encoding vary for each piece of information?

There are different encoding mechanisms for representing data, and different ways of compressing the encoded data. If Kolmogorov complexity was encoding agnostic, then wouldn't the shortest computer program to describe each information be "0" or "1" and a call to the encoding system where each encoding system maps "0" or "1" to pieces of information of arbitrary length (the number of encoding systems would be $\frac{n}{2}$, where $n$ is the umber of pieces of information being considered). We could also increase the length of the description string, and reduce the number of encoding systems, but I think my point stands. This seems like a trivial notion of Kolmogorov complexity--is there anything I'm missing?

Improve this question
$\endgroup$
1
  • $\begingroup$ Aren't you just raising the problem an order? Your way, there's a one-to-one correspondence between strings and encoding schemes, with each encoding scheme representing the characteristic function of its associated string. So the program complexity is now just: given a string, determine which encoding scheme represents it. And as YuvalFilmus pointed out, that complexity will necessarily be the same (modulo a constant) as the string's Kolmogorov complexity (in its original, say binary or ascii, etc, encoding). $\endgroup$
    – John Forkosh
    Jul 12, 2017 at 0:33

2 Answers 2

Reset to default
3
$\begingroup$

The formal version of your statement is known as the invariance theorem, which states (informally) that any two definitions of Kolmogorov complexity differ by at most a constant. This issue is covered on any textbook or lecture notes on Kolmogorov complexity.

Improve this answer
$\endgroup$
0
$\begingroup$

What I think you might be getting at is something like the following: One might get the bright idea of building a lot of complexity into a given universal Turing machine. Let's say that we make it so that the quicksort algorithm only requires a few bits. Hey, maybe there are other algorithms we can similarly build in as well! One problem is that the more we do this, the fewer short codes there are to map to them. All the other operations start to pay the price. It's like trying to get everyone rich by rigging the lottery for each person in town. Each time someone gains big, many more lose a little. It's possible that some restrictions could be placed on universality, so that no nontrivial algorithms have a lot of mutual information with a purported universal machine, but I don't think that is necessary for the Invariance Theorem.

There just have to be diminishing returns on "cheating"--that is, when universal machines have lots of unnecessary bells and whistles that go beyond being 'Turing complete.' You'll be able to reduce the apparent K-complexity of the code, but unless you handpick your universal machine to do so, you won't know whether a program could be encoded with a deceptively small code because the only way for that to happen is to smuggle some sophisticated algorithms into the given universal machine just for that purpose. Your universal machine is specialized now for making certain kinds of programs really small by allowing many more programs to be much bigger than they need to be for most universal machines.

Looking at it another way, I could write a special version of UnZip that would produce the entire contents of Windows 10 when it "unzips" a special 8-byte long code. But it is not really unpacking information from the input, it would already have almost the entire contents of Windows 10 built-in already. This zipping utility would be substantially larger than comparable unzip utilities, and it would not demonstrate that the K-complexity of Windows 10 is 8 bytes.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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