# Kolmogorov (Kolmogoroff-) Complexity, Contradiction with Invariance Theorem.

Fix some programming languages $S$ which is rich enough such that one can write interpreters for $S$ in $S$. Define $$K(w) := \mbox{length of a shortest program producing w}.$$ Now fix some program $P$ in $S$ and define $$K_P(w) := \mbox{length of a shortest input to P such that P produces w}$$ and $K_P(w) := \infty$ if no such input exists.

The second definition is the usual one for the (unconditional) Kolmogorov complexity. Now for this the famous Invariance Theorem holds, namely:

There exists some programm $U$ such that for all $P$ and $w$ we have $$K_U(w) \le K_P(w) + C_P$$ where the constant $C_P$ just depends on $P$. Such a program is called universal and these programs are precisely the interpreters. The proof works by coding $P$ and $w$ for $U$, the coding of $P$ goes into the constant. A corollary of this is that for two universal programms $U, V$ we have $$-C_{U,V} \le K_U(w) - K_V(w) \le C_{U,V} \qquad (*)$$ where the constant $C_{U,V}$ just depends on $U$ and $V$.

But now if I have a shortest program $P$ for $w$ (without any input), then $K(w) = |P|$, but also $K_U(w) = |P|$ for each universal $U$, because this $P$ is the shortest program and therefore the shortest input which when interpreted as a program and executed yields $w$, therefore $$K_U(w) = K(w)$$ for each universal $U$, but this yields $K_U(w) = K_V(w)$ for all universal $U,V$ contradicting (*), so what goes wrong here. Maybe there is something wrong with the definition of $K(w)$ but I cannot see what, I have just defined it with relation to some programming language $S$, which should be fine?

• $-C_{U,V}\le 0 \le C_{U,V}$ is a contradiction because...? – Martín-Blas Pérez Pinilla Feb 26 '14 at 18:44
• It is not a contradition, but it is a stronger claim, which if it holds would be mentioned in the literature. But there just the weaker invariance theorem is mentioned. – StefanH Feb 26 '14 at 19:02
• "$K_U(w)=|P|$ for each universal $U$... and therefore the shortest input" is highly doubtful. – Martín-Blas Pérez Pinilla Feb 26 '14 at 22:59
• Think it should sound "$P$ is a shortest program in $S$", but if $U$ is an interpreter for example for JAVA or even a variant of $S$ enriched to some "syntactic sugar" than there might be some possible shorter program for $U$ producing $w$, so this conclusion holds for all interpreters which interpret exactly $S$, but there might be still interpreters for other languages. I saw my error, now everything is clear. – StefanH Feb 27 '14 at 11:44

If a program $U$ is universal, so is the program $U'$ defined so that for all $\sigma$, $U'(0\sigma) = U(\sigma)$ and $U'(1\sigma) \uparrow$. But it is never the case that $K_U(\tau) = K_{U'}(\tau)$ for any $\tau$. So there is an error in the argument in the question.
• The essential error in the question is that you cannot pass the same program to two different interpreters. So if you define $S$ using Java, and $U$ is C++, and $P$ is the shortest Java program outputting a string, there is no reason to think that the shortest C++ program outputting that string is of the same length, much less that $P$ is somehow also a valid C++ program. – Carl Mummert Feb 27 '14 at 3:54