0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ $-C_{U,V}\le 0 \le C_{U,V}$ is a contradiction because...? $\endgroup$ – Martín-Blas Pérez Pinilla Feb 26 '14 at 18:44
  • $\begingroup$ 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. $\endgroup$ – StefanH Feb 26 '14 at 19:02
  • 1
    $\begingroup$ "$K_U(w)=|P|$ for each universal $U$... and therefore the shortest input" is highly doubtful. $\endgroup$ – Martín-Blas Pérez Pinilla Feb 26 '14 at 22:59
  • $\begingroup$ 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. $\endgroup$ – StefanH Feb 27 '14 at 11:44
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Carl Mummert Feb 27 '14 at 3:54

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.