Re:Kolmogorov Complexity and Our Search for Meaning
by Xcelerate on Friday August 03, 2018 @04:44PM
(#17683460)
The 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.
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.