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)$?

  • $\begingroup$ What is an elegant program? $\endgroup$ Apr 24, 2017 at 18:24
  • 1
    $\begingroup$ @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. $\endgroup$ Apr 24, 2017 at 18:31
  • 4
    $\begingroup$ 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))$. $\endgroup$ Apr 24, 2017 at 19:13


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.