It is well known that the Kolmogorov complexity is uncomputable in Turing-complete programming languages. However, what about total programming languages?

For example, is the Kolmogorov complexity of natural numbers computable if we work in Gödel's System T? (I suppose not, but I don't have a proof.) Furthermore, is it known what is the strongest computational model in which the Kolmogorov complexity is computable?

  • 2
    $\begingroup$ In any "reasonably" total programming language, you can just start enumerating all programs from "shortest" to "longest" and executing them until one produces the desired output. The "Kolmogorov complexity" will then be the length of the first program that produces the given output. $\endgroup$ – Derek Elkins Jan 24 at 4:50

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.