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.


In detail, consider the following sentence:

The least string that is not output in N steps by any program of length $\le 2n$, where N = runtime of program p.

 where p is a program of length $\le n$, whose runtime is the longest among all programs of length $\le n$. That is, it's an n-Busy Beaver Runtime champion.

The string $x$ described by that sentence has Kolmogorov complexity $K(x) \le n + \log_2(x) + C$, where $n$ comes from $p$, $\log_2(x)$ comes from $n$, and $C$ comes from the rest of the sentence.

If $n$ is big, such that $2n >  n + \log_2(x) + C$, the string $x$ thus described has a minimal program that has length $<  2n$, which, by the description of $x$, must have runtime longer than the n-Busy Beaver Runtime champion.

Further, $x$ is short, that is, $l(x) \le 2n + 1$, since there are only so many possible outputs from programs with length $\le 2n$.

Thus, this following program calculates a function that dominates over the Busy Beaver Runtime function for all big n:

Input n.
List all strings $x$ of length $\le 2n + 1$.
For each $x$, get its Kolmogorov complexity $K(x)$ using the oracle. 
Run each program of length $K(x)$, until one of them outputs $x$. Record the runtime as $n_x$.
After all the $n_x$ are recorded, output the biggest one.

From this, a program that dominates over Busy Beaver Runtime function for all n can be constructed, which can be used to calculate Busy Beaver Runtime function, which can be used to solve the halting problem.