1
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ What is an elegant program? $\endgroup$
    – Yuval Filmus
    Commented 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$
    – David Richerby
    Commented 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$
    – David Richerby
    Commented Apr 24, 2017 at 19:13

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.