2
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 13, 2016 at 9:08
  • $\begingroup$ 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$. $\endgroup$
    – Don Arturo
    Mar 13, 2016 at 11:31
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 13, 2016 at 11:35

1 Answer 1

1
$\begingroup$

I guess, I have found the answer myself: no.

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.

$\endgroup$
5
  • $\begingroup$ Any opinions, is this correct? $\endgroup$
    – Don Arturo
    Mar 13, 2016 at 13:20
  • $\begingroup$ Why is $K(p) \geq l(q) + l(s) + O(1)$? $\endgroup$ Mar 13, 2016 at 19:31
  • $\begingroup$ 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$. $\endgroup$
    – Don Arturo
    Mar 14, 2016 at 3:31
  • $\begingroup$ 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. $\endgroup$ Mar 14, 2016 at 7:16
  • $\begingroup$ 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. $\endgroup$
    – Don Arturo
    Mar 14, 2016 at 11:53

Your Answer

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

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