# Computability of Kolmogorov complexity in total languages

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?

• 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. – Derek Elkins Jan 24 at 4:50