I don't get it, why couldn't you "simply" iterate through every program shorter than the string you're trying to compress, compiling and running each while discarding the ones with the wrong output and halting when you either find a working program or run out of shorter strings to try?
Edit: Oh, I get it now, you can't tell whether or not a given long-running program will eventually produce the target string without solving its halting problem.
Exactly right! I kinda think that these non-computable problems are all sort-of the same problem, just viewed from different angles.
> It is straightforward to compute upper bounds for K(s) – simply compress the string s with some method, implement the corresponding decompressor in the chosen language, concatenate the decompressor to the compressed string, and measure the length of the resulting string – concretely, the size of a self-extracting archive in the given language.
This is analogous (but not exactly) to the Travelling Salesman Problem: we “can’t” (in the case of Kolmogorov complexity, literally cannot) get the exact number, but getting a nearly perfect estimate of the number has cheap-and-easy algorithms.
It’s fun to think about what an exact solution to computable Kolmogorov complexity would “mean”, though, sort of like it’s fun to think about the consequences of https://en.wikipedia.org/wiki/Hypercomputation: as a consequence of calculating the Kolmogorov complexity, you’d be optimally compressing the input data, identifying every possible nuance of self-similarity in the input, no matter on what level of abstraction it occurred. The intermediate model of the informational content required to construct the compressor would be immense—possibly a description of all mathematical theorems in the relevant axiom system, and all scientific laws governing the relevant generator-of-structure (e.g. physics, chemistry, biology, human psychology, etc.) Such a system really could “understand the universe from a grain of sand.”
"If you know the output you'd like, it's impossible to know how much code it will take to get there."