Several commenters have remarked that the alt-complexity and K-complexity differ only up to a constant. I have now written a post where I write down a detailed proof of that classical result, which is known as the “coding theorem”.
Several commenters have remarked that the alt-complexity and K-complexity differ only up to a constant. I have now written a post where I write down a detailed proof of that classical result, which is known as the “coding theorem”.