# Does the Kolmogorov complexity of a program $p$ generating a string $x$ equal the complexity of $x$ up to constant?

If $U$ is a universal prefix Turing machine, $U(p)=x$ for some program $p$ and string $x$, is it true that $K(x)=K(p)+O(1)$, with $K$ being the prefix Kolmogorov complexity?

• What do you think? Do you have a guess? Can you prove your guess? We're not here to do your homework for you, but rather to help you complete it on your own. Mar 13, 2016 at 9:08
• Sorry, I am new to this website and also, being a physicist, new to this field of research. Nevertheless, that's not a reason to be unfriendly. I guess, the answer is no, since $p$ can contain some random, incompressible noise, that blows up $K(p)$ while not helping to compute $x$. Mar 13, 2016 at 11:31
• I'm sorry if you got this impression. We're here to help you understand the material, but you also have to make some effort, and to let us know what you tried and where you got stuck. Mar 13, 2016 at 11:35

Let $q$ be a shortest program that generates $x$: $K(x)=l(q)$. It is enough to concatenate any incompressible string $s$ not sharing information with $q$ and setting $p=\bar{q}s$. Let $m$ be the number of a Turing machine $T_m$ in the standard enumeration, that takes $p$, executes $q$ and discards $s$. Then, $U(\langle m,p\rangle)=T_m(p)=x$. However, $K(p)\ge l(q)+l(s)+O(1)>l(q)=K(x)$. We thus have constructed a $p$ that contradicts the claim.
• Why is $K(p) \geq l(q) + l(s) + O(1)$? Mar 13, 2016 at 19:31
• Because $q$ and $s$ are incompressible in do not contain mutual information, by construction of $s$: $K(s|q)=K(s)$ and $K(q|s)=K(q)$. The bigger sign is because we have to encode the length of $q$ as well since $p$ contains a self-delimiting version of $q$. Mar 14, 2016 at 3:31
• I read $K(x) = K(p) + O(1)$ as an inequality – $K(x) \leq K(p) + C$ for some constant $C$ depending on $U$. Under this interpretation, the statement appears to be correct. What you show is that the opposite inequality can fail. Mar 14, 2016 at 7:16
• Your inequality is trivially correct. The equation $K(x)=K(p)+O(1)$ implies that there is a constant $D$ such that $|K(x)-K(p)|\le D$, which appears not to be true. So, I'm glad that you confirm my reasoning, that the opposite inequality does not hold in general. Mar 14, 2016 at 11:53