We assume that reader is familiar with the notions of undecidability, Turing reductions, Kolmogorov complexity, Halting problem, and related subjects.

The (easy) proof that the uncomputability of Kolmogorov complexity implies the undecidability of the Halting problem can be found in many lectures notes and books; usually the proof assumes that the Halting problem is decidable and derive the  computability of Kolmogorov complexity which is a contradiction. In other words given an oracle for the Halting problem, we can compute the Kolmogorov complexity of a string $x$.

But we can also derive the uncomputability of Kolmogorov complexity from the undecidability of the Halting problem; the proof is “less popular” but nevertheless can be found after a few searches on Google. For example the technical report: Gregory J. Chaitin, Asat Arslanov, Cristian Calude: Program-size Complexity Computes the Halting Problem. Bulletin of the EATCS 57 (1995) contains two different proofs, and the great book Li, Ming, Vitányi, Paul M.B.; An Introduction to Kolmogorov Complexity and Its Applications presents it as an exercise (with a hint on how to solve it that is credited to P. Gács by W. Gasarch in a personal communication Feb 13, 1992). Here we give an extended proof, with more details, that the Halting problem can be decided using an oracle that computes the Kolmogorov complexity of a string, i.e. that the Halting problem is Turing reducible to the Kolmogorov complexity. Continue reading →