Kolmogorov complexity is Turing equivalent to the halting problem

This post describes several Turing equivalent problems to the halting problem: the busy beaver problem, the busy beaver runtime problem, the minimal program problem, and the Kolmogorov complexity problem.

But really, only one part of the proof is hard, and that is proving that the halting problem can be Turing-reduced to the problem of calculating Kolmogorov complexity.

The core of the argument is this: there exists short strings with short minimal programs, whose runtime is insanely long. That's really it.