# Is $K(b|a) \geq 1$ if $a\neq b$?

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?

• Are you solving an exercise sheet on elegant programs? – Yuval Filmus Apr 24 '17 at 19:41
• No, these are premises in a proof I am working on, and I'm verifying my reasoning is correct. – 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$.