3 ms·
Kolmogorov Complexity is not a single explicitly-defined function: it depends on your model of computation. For large strings, this doesn't matter very much, be
by xamuel 8y ago
Kolmogorov Complexity is not a single explicitly-defined function: it depends on your model of computation. For large strings, this doesn't matter very much, because if you have a program of length n in one Turing complete programming language L1, it only takes O(1) extra code to transform your program into a program in another Turing complete programming language L2 that does the same thing.
However, for small strings, the actual complexity you compute starting from any particular model of computation is totally dwarfed by that O(1) padding cost. So, actually computing Kolmogorov complexities of small strings is basically just pointless trivia.
- Xcelerate 8y agoThe O(1) "language" term is discussed in the linked article. The authors use Levin’s semi-measure, which constitutes the Universal Distribution, in combination with the Coding Theorem to approximate a KC that is independent of any specific Turing machine.