# Joint Kolmogorov complexity of elegant programs

If $a$ and $b$ are different elegant programs (minimal program for some output), is their joint Kolmogorov complexity the sum of their individual complexities, i.e. $K(a,b) = K(a) + K(b)$?

• What is an elegant program? Apr 24, 2017 at 18:24
• @YuvalFilmus A Turing machine $M$ is elegant if $|\langle M\rangle|\leq|\langle M'\rangle|$ for every other Turing machine $M'$ that computes the same function. Apr 24, 2017 at 18:31
• I'd expect the answer to be "no". Most strings are incompressible, so it should be possible to find two very similar strings for which the shortest program is just print "The string". But, now, the shortest program that prints both strings is essentially print "The string" twice except make these small changes the second time, giving $K(a,b) = K(a) + \text{a bit} \ll K(a)+K(b)\approx 2K(a)$. In general, $K(a,b)=K(a)+K(b|a)+O(\log K(a,b))$. Apr 24, 2017 at 19:13