And yet, we can fairly-easily
upper-bound Kolmogorov complexity (often, we believe, quite tightly, though we can’t know for sure.) Quoting Wikipedia:
> 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.”