The author is not including the machine size. From wikipedia: "We could, alternatively, choose an encoding for Turing machines, where an encoding is a functio

The author is not including the machine size. From wikipedia: "We could, alternatively, choose an encoding for Turing machines, where an encoding is a function which associates to each Turing Machine M a bitstring <M>. If M is a Turing Machine which, on input w, outputs string x, then the concatenated string <M> w is a description of x. For theoretical analysis, this approach is more suited for constructing detailed formal proofs and is generally preferred in the research literature. In this article, an informal approach is discussed." If you consider the length of the Turing machine and the input string, then your don't get K = 0. The author's approach only includes the size of w, which is always 0. How big are the machines used by the author's silly approach? If we wanted to describe the machine that prints "abababababbaba", we could write the program/specification as: (1) Use the machine L_silly_abababababbaba (2) Use the string '' How can we encode this into a shorter program/specification? Maybe by concatenating the machine name and ''? L_silly_abababababbaba '' Or we can be clever and realize that the string is always '' so we just need to machine name L_silly_abababababbaba Or we can say we don't need the L_silly_ abababababbaba Can we go shorter? What if we specify a gzipped version of the string? We can take the string, unzip it, and use that Turing machine. But most strings are not compressible via gzip. So there will be many strings for which the shortest program via this approach is: abababababbaba ... and some of the other words in this posted comment...