|
> one is not allowed to take a separate Language for each input They're not defining a different language per input, they're defining a single language, but it's "silly" because it's tailored to favour one specific string. Their point is that we can always construct a universal language which encodes any particular sequence as 1 bit: the language simply checks the first bit of its input, and if it's 0 it returns that sequence; otherwise it ignores that bit and interprets the rest of the input as some "non-silly" universal language (Ruby, in their case). Kolmogorov Complexity normally tries to ignore the particular choice of language (since, in principle, any turing-complete language can emulate any other with a constant (but probably large) overhead). Their point is that language choice matters a lot, since there's nothing to prevent us choosing a universal language which just-so-happens to favour some outputs much more than others. I get what they're saying, but there are solutions to this, in particular minimal languages like Binary Lambda Calculus, Binary Combinatory Logic, Wolfram's 2/3 turing machine, the rule 110 cellular automaton, Brainfuck, etc. These are akin to "nothing up my sleeve numbers" used in cryptography (where the choice of parameter is pretty much arbitrary, but technically there are certain "silly" choices that would undermine the security) |