What would the K program for those two sequences look like and why would one be much different than the other?
Could you point me to a definition of Kolmogorov complexity that effectively deals with short encodings?
My understanding is that Kolmogorov complexity is only theoretically relevant when the number of bits in the encoding is much longer than the program required to emulate one Turing machine equivalent on another. For instance, a LISP interpreter is 90 lines of Python – about 4kB. Therefore a relevant length would be much larger than 4kB.
I know of one way short encodings might be addressed by a more recent take on Kolmogorov complexity:
Marcus Hutter’s AIXI theory (circa 2000) reified something he called a “natural Turing machine” as the basis of Kolmogorov complexity which is, itself, the basis of Solomonoff induction.
This “natural” Turing machine gets around the constant additive factor of 4k (or thereabouts) and permits one to compare short K programs without bias.
The “natural Turing machine” is, in some sense, the “simplest” computer (Turing machine equivalent). Defining the degree of simplicity of a computer does seem to beg the question but it has intuitive appeal.
I think I may have a way to actually define Hutter’s natural Turing machine in operational terms – which is to say it must involve physical laws so that the computer can emulate itself, minus some memory capacity and speed. The length of the emulation program – on that computer – would be a measure of that computer’s “natural Kolmogorov complexity”.
Having said that, I don’t see that such a minimal computer would result in greatly differing lengths of programs outputting the two short encodings:
Indeed, it seems the shortest programs for those strings would be, of identical length: