Since $K(a|a) = 0$, is $K(b|a) \geq 1$ when $a\neq b$, as we need at least one bit to distinguish between $K(a|a)$ and $K(b|a)$? If not true in general, is it true if $a$ and $b$ are elegant programs?

  • $\begingroup$ Are you solving an exercise sheet on elegant programs? $\endgroup$ – Yuval Filmus Apr 24 '17 at 19:41
  • $\begingroup$ No, these are premises in a proof I am working on, and I'm verifying my reasoning is correct. $\endgroup$ – yters Apr 24 '17 at 19:49

Whether $K(a|a) = 0$ could depend on your universal computer. The only thing you can say in general is that $K(a|a) \leq C$ for some constant $C$ independent of $a$.

You can arrange for a universal computer for which $K(a|a) = 0$ for all $a$, and then indeed $K(b|a) > 0$ for all $b \neq a$, since there is only one program whose length is zero, and given $a$ it generates $a$.


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.