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$ – Yuval Filmus Apr 24 '17 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$ – David Richerby Apr 24 '17 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$ – David Richerby Apr 24 '17 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.