It's a theorem that, although the Kolmogorov complexity of a string is relative to the Turing machine you're working with, it differs by at most a constant (basically the amount of space it takes to write an interpreter for Turing machine A inside of Turing machine B).
My question is: how does this theorem deal with the issue of Turing machines with purposefully inefficient encodings?
For example, suppose we have a universal Turing machine $M_{terrible}$ that requires its input to be repeated five times. It starts by verifying that the input is in fact of the form x ++ x ++ x ++ x ++ x
, then executes the universal Turing machine $N$ on just x
. Shouldn't this force the Kolmogorov complexity of strings relative to $M_{terrible}$ to be 5 times larger than they are relative to $N$? Why doesn't this violate the theorem?