Yes, the Kolmolgorov complexity of a string X is the minimum length of a program/string that when fed into an efficient universal computer will yield back the s

Yes, the Kolmolgorov complexity of a string X is the minimum length of a program/string that when fed into an efficient universal computer will yield back the string X. The Kolmolgorov complexity of a string is also undecideable - it's essentially equivalent to the halting problem. "Best Lossy Compression" is ambiguous - how much loss is acceptable is isn't defined in the phrase.