Kolmogorov complexity is undecidable because the halting problem is undecidable. If we could solve Kolmogorov complexity we could do Solomonoff induction and b

Kolmogorov complexity is undecidable because the halting problem is undecidable. If we could solve Kolmogorov complexity we could do Solomonoff induction and build AIXI and solve (at least one formulation of) decision theory. The real problem (imo) is that proof search is also undecidable (either directly from halting problem or similar argument) and so there isn't a procedure we can write that identifies trick programs to exclude as special cases. There are an infinite number of various trick programs for which halting is undecidable and recognizing them is undecidable.