Yes, you need some overhead for specifying string literals. For a binary string x of length n, you have KS(x) <= n + O(1) for simple Kolmogorov complexity (wher

Yes, you need some overhead for specifying string literals. For a binary string x of length n, you have KS(x) <= n + O(1) for simple Kolmogorov complexity (where one program can be a prefix of another), and KP(x) <= n + KP(n) + O(1), for the prefix Kolmogorov complexity, in which programs must be prefix-free. In this paper [1] of mine, you can find explicit definitions of KS and KP, as well as the theorems above, with specific constants instead of O(1). [1] https://tromp.github.io/cl/LC.pdf https://tromp.github.io/cl/LC.pdf