My understanding is that the undecidability of the halting problem is equivalent to the undecidability of the decision version of compression (does a given stri

My understanding is that the undecidability of the halting problem is equivalent to the undecidability of the decision version of compression (does a given string have a Kolmogorov representation, or not). They're saying the same thing and mathematically equivalent to Godel's incompleteness as well. The difference is that with data compression, you don't get random-looking inputs and would explain why text, voice, image domains are amenable to compression algorithms. In contrast, the state space of programs is exponential in the budget N and looks very random. The exponential explosion makes the analysis very inefficient relative to hardware ability. And then the random-looking state sequences are especially not very compressible. These characteristics are harder to leverage. The pigeonhole principle works for lossless compression but I don't see the analog to Halt or Rice's theorem, etc.