There is a universal metric of information: amount of bits. It's universal in the sense that if we write a piece of information in DNA (4-ary digits), we can simply multiply by 2-log-4 to get the amount of bits.

I'm wondering if there is also a universal measure of the size of a program. I know about Kolmogorov complexity, but this is defined in terms of the size of a Turing machine.

But if we compare this to some other computational model, will the equivalent complexity measure be equivalent to the Kolmogorov complexity measure, in the same way that the 4-ary information metric is equivalent to the binary one?

For example, suppose instead of a Turing machine we used a modern CPU, and we define a similar metric of the size of programs, will it agree with Kolmogorov complexity?

I think what I mean by the metrics being equivalent is that there is one canonical metric for each universal model of computation, and that the order of complexity of programs is the same in each model of computation, or even that it is some scalar multiple of it.

  • $\begingroup$ The Kolmogorov complexity is defined for predetermined programming language and model. Besides it is uncomputable, so how the results could be compared? The invariance theorem probably already covers the second part. $\endgroup$ – Evil Apr 17 '18 at 9:34
  • $\begingroup$ @Evil, what invariance theorem? $\endgroup$ – user56834 Apr 17 '18 at 10:00
  • $\begingroup$ "I know about Kolmogorov complexity, but this is defined in terms of the size of a Turing machine." -- So? You are fine with transforming anything into binary strings, so why do you have an issue with transforming into TMs? (Note that transformation into binary is a lot less unambiguous if you don't start with a power of 2 as base, let alone things other than plain numbers.( $\endgroup$ – Raphael Apr 17 '18 at 10:08
  • $\begingroup$ The Invariance Theorem about constant in Kolmogorov Complexity. $\endgroup$ – Evil Apr 17 '18 at 11:35

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.