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.

Aitken's trick for calculating decimal expansions of rationals

Aitken's Method

Professor Aitken was both a mental calculator and a master mathematician, and a detailed account of his mental math abilities is found in An exceptional talent for calculative thinking, (IML Hunter, 1962)

I'd just like to sketch out one amazing trick, which is illustrated thus:


The proof is  $x = 5/23 = 15/69$, then, $x = (15 + x) /70$, so the trick is to calculate $15/70$ by short division, to generate the digits of $x$ one at a time, then immediately feed to the top to continue. A kind of "just-in-time" algorithm!