The invariance theorem of kolmogorov complexity states that for two different languages with complexity functions $K_1$ and $K_2$, we have

$$\exists c.\forall s. K_1(s) \le K_2(s) + c$$

Here is an apparent paradox I found. Let the two languages be Binary Lambda Calculus and (an idealized version of) Perl, with complexity functions $K_L$ and $K_P$ respectively. I could have used other languages, but these were the easiest. Both will measure the length of the minimal program in bits.

By the invariance theorem, there exists a $c$ such that:

$$\forall s. K_L(s) \le K_P(s) + c$$

This seems reasonable. After all, we can create an (idealized) Perl interpreter in BLC. Call this interpreter $e$. Also, for a perl program $p$, there is a BLC term encoding $p$, say $t_p$. Then the program


Computes the same string as $p$. This seems to imply that $c$ can equal $2 + |e| + |p|$, proving the invariance theorem for this specific case.

But actually, $t_p$ will be longer than $p$, since BLC does not encode binary data efficiently, so the above analysis does not work. Perl, on the other hand, can encode binary data efficiently.

In particular, a perl program can include the __DATA__ token, followed by arbitrary binary data. The program will then have access to this data. Note that no escape codes are necessary, as would be in a Perl string, since after seeing the __DATA__ token, perl only interprets the rest of the program as raw binary data. There is no way to "recover" from this. This __DATA__ token will be important.

Now, for the paradox. For any string $s$, we can create a perl program $p_s$ such that $|p_s| = |s| + c_P$, where $c_P$ is a constant independent of $s$ and $p_s$. This is because we can have a perl program that outputs the raw data after __DATA__. We then store the string $s$ directly in __DATA__.

Now, we will create a BLC program as follows. Let $r$ be a BLC term that takes two strings, and outputs $<s_1s_2, |s_1|>$, where $< \cdot , \cdot >$ is a pairing function.

Now, it is easy to show that there exists a string $s$ and a number $n$ such that $|s| > n$ and $K_L(s,n) \gt |s| + x$ for any constant $x$. Let $x$ equal $8 + |r| + 2c_P + 2|e| + 2c$.

Let $s_1$ be the first $n$ characters of $s$ and $s_2$ the rest of $s$. Then the BLC program $0101r01et_{p_{s_1}}01et_{p_{s_2}}$ outputs $<s,n>$, meaning that $$K_L(s,n) \le |0101r01et_{p_{s_1}}01et_{p_{s_2}}| \le 4 +|r| + 2 + |s_1| + c_P + |e| + c + 2 + |s_2| + c_P + |e| + c = |s| + x$$ a contradiction!

So, what is the resolution?

It seems that the main problem is that BLC is a prefix free language, whereas Perl is not.

Perl's __DATA__ token, a key part of the paradox, implies the Perl is not prefix free. That is because for any program with a __DATA__ token, you can add whatever bytes you like to the end of the program. Taking the contrapositive, BLC being prefix free implies that it can not encode raw binary data. The paradox should work with any prefix free and non-prefix free language.

Another thing to touch on is that Perl deals only with bytes, not bits. We can assume that idealized Perl can deals with individual bits. Or we can hardcode into $p_s$ with how many bits of the last byte to ignore, which only add a constant overhead (up to 7 bits for the useless bits at the end of the last byte, and a couple of bytes to slice the bits of the end of last byte).

  • 1
    $\begingroup$ There are two types of Kolmogorov complexity, as you mention: prefix-free and non-self-delimiting. Also, not all programming languages are necessarily “admissible” for Kolmogorov complexity. $\endgroup$ – Yuval Filmus Dec 9 '18 at 7:57
  • $\begingroup$ @YuvalFilmus I suspected as much. The weird thing is most texts on Kolmogorov complexity do not seem to discuss this at all. For example, en.wikipedia.org/w/… does not discuss it all, implying that any programming language is fine. It even implies that Lisp, Pascal, and Java are fine, even though I'm pretty sure that wouldn't be "admissible". $\endgroup$ – PyRulez Dec 9 '18 at 23:02
  • $\begingroup$ @YuvalFilmus Do you know of a text that treats Kolmogorov complexity probably, keeping in mind the difference between languages? Also, does the Invariance theorem apply to prefix-free languages among themselves? $\endgroup$ – PyRulez Dec 9 '18 at 23:03
  • 1
    $\begingroup$ The standard text is Li and Vitanyi. It should contain everything you need to know. $\endgroup$ – Yuval Filmus Dec 10 '18 at 0:13

Your Answer

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

Browse other questions tagged or ask your own question.