4 ms·
I think the author's point is that K(s) is the shortest program in _any_ language. Thus for any string s there exists a language ("silly,s") that produces the p
by Eyas 12y ago
I think the author's point is that K(s) is the shortest program in _any_ language. Thus for any string s there exists a language ("silly,s") that produces the program with length 0 (or 1).
- vilhelm_s 12y agoBut this just misunderstands the definition. In the standard definition you pick _some_ Turing-complete language, and then define K(s) with respect to that language. You can then go on to show that in the limit of longer and longer strings, it does not make much difference which language you pick.
- acchow 12y agoPrecisely. The author defines language as a mapper from input to output, which is necessary but not sufficient. Its L_silly (written in Ruby) is not a language since it uses "eval" which depends on the entirety of Ruby.