Proof for Kolmogorov complexity is uncomputable using reductions

Question

I am looking for a proof that Kolmogorov complexity is uncomputable using a reduction from another uncomputable problem. The common proof is a formalization of Berry's paradox rather than a reduction, but there should be a proof by reducing from something like the Halting Problem, or Post's Correspondence Problem.

Answer 1

You can find two different proofs in:

Gregory J. Chaitin, Asat Arslanov, Cristian Calude: Program-size Complexity Computes the Halting Problem. Bulletin of the EATCS 57 (1995)

In Li, Ming, Vitányi, Paul M.B.; An Introduction to Kolmogorov Complexity and Its Applications it is presented 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).

** I decided to publish an extended version of it on my blog.

Answer 2

This was a fun question to think about. As described in the other answer and the comments below, there is a Turing reduction from the Halting problem to computing Kolmogorov complexity, but notably there is no such many-one reduction, at least for one definition of 'computing Kolmogorov complexity'.

Let's formally define what we're talking about. Let $HALT$ denote the standard language of TM's that halt when given a description of themselves as input. Let $KO$ denote $\{ \langle x,k \rangle \mid x \text{ has Kolmogorov complexity exactly } k \}$.

Assume that $HALT \le KO$ by some many-one reduction. Let $f: \{0,1\}^* \rightarrow \{0,1\}^*$ denote the function that this reduction computes. Consider the image of $HALT$ under $f$, which I will denote $f(HALT)$.

Note $f(HALT)$ consists of strings of the form $\langle x,k\rangle$ where $x$ has Kolmogorov complexity exactly $k$. I claim that the $k$'s that occur in $f(HALT)$ are unbounded, as there are only a finite number of strings with Kolmogorov complexity exactly $k$, and $f(HALT)$ is infinite.

Since $HALT$ is recursively enumerable (aka Turing-recognizable in some books) it follows that $f(HALT)$ is recursively enumerable. Combined with the fact that the $k$'s are unbounded, we can enumerate $f(HALT)$ until we find some $\langle x,k\rangle$ with $k$ as large as we want; i.e. there exists a TM $M$ that on input $k$ outputs some element $\langle x,k \rangle \in f(HALT)$.

Write a new TM $M'$ that does the following: first, compute $|M'|$ using Kleene's recursion theorem. Query $M$ with input $|M'|+1$ to get $\langle x, |M'|+1\rangle \in f(HALT)$. Output $x$.

Clearly the output $x$ of $M'$ is a string with Kolmogorov complexity at most $|M'|$ but $\langle x, |M'|+1\rangle \in f(HALT)$ which is a contradiction.

I believe you can also substitute in the problem "Kolmogorov complexity exactly $k$" with "Kolmogorov complexity at least $k$" with minor changes.