[catlifeonmars]

> The uncomputability of both arises directly from the Halting Problem

This is perhaps pedantic, but this statement is a little misleading. Kolmogorov complexity and the halting problem both describe the same concept in different formulations. One could just as easily say that the halting problem arises directly from Kolmogorov complexity.

[scythe]

More generally, both are cases of a diagonal argument.