# Proof for Kolmogorov complexity is uncomputable using reductions

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.

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.

• Furthermore, Chaitin's proof (in that link) shows that the oracle queries can be made in parallel. $\;\;\;\;$ – user6973 Apr 30 '15 at 1:07
• Are these proofs are really Turning reductions (one to one (or) one to many) ? I am confused !! please help me – Krishna Chikkala May 1 '15 at 6:04
• @KrishnaChikkala: the first is surely a Turing reduction. I found it not so clear, so I decided to publish an extended version of it on my blog. If you want take a look at it (and tell me by email if you think that it can be improved). Also note that Turing reductions are different from many-one reductions (which are "stronger" reductions); indeed Joe Bebel's answer proves that such reduction cannot exist. – Marzio De Biasi May 1 '15 at 17:07

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.

• But what about a Turing reduction? – Sasho Nikolov Apr 27 '15 at 8:05
• Let me throw out this idea in a comment because I haven't thought through the idea. Let the decision problems be the same but the reduction is now a Turing reduction $R$. Consider the set $S$ of all $\langle x,k\rangle \in KO$ such that there exists some TM in $HALT$ that causes $R$ to query the $KO$ oracle on input $\langle x,k\rangle \in KO$. I claim $S$ has the same unbounded $k$ property (this needs to be justified a bit more than I am stating) and $R$ can be used to construct such unbounded $\langle x,k\rangle$, which is always a contradiction. – Joe Bebel Apr 27 '15 at 8:16
• Actually I retract that $R$ can be used in that way. It is not so clear in the Turing reduction context. – Joe Bebel Apr 27 '15 at 9:41
• A few places claim that Kolmogorov complexity is Turing equivalent to the Halting problem, for example Miltersen's notes daimi.au.dk/~bromille/DC05/Kolmogorov.pdf. If that's true, there must be a Turing reduction. By the way a Turing reduction from Kolmogorov complexity to the Halting Problem is easy and gives a different proof that halting is undecidable. – Sasho Nikolov Apr 27 '15 at 17:16
• $HALT\le_T KO$ follows from the arguments given in the link in the other answer. In fact, since the other reduction is (almost) trivial, we have that $HALT\equiv_T KO$. – user30585 Apr 29 '15 at 21:03