<p>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'.</p>

<p>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 \}$. </p>

<p>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)$. </p>

<p>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.</p>

<p>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)$.</p>

<p>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$.</p>

<p>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.</p>

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

CC BY-SA 3.0
2015-04-27T08:05:15.777Z
But what about a Turing reduction?
Sasho Nikolov
CC BY-SA 3.0
2015-04-27T08:16:53.207Z
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
CC BY-SA 3.0
2015-04-27T09:41:59.727Z
Actually I retract that $R$ can be used in that way. It is not so clear in the Turing reduction context.
Joe Bebel
CC BY-SA 3.0
2015-04-27T17:16:01.837Z
A few places claim that Kolmogorov complexity is Turing equivalent to the Halting problem, for example Miltersen's notes http://www.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
CC BY-SA 3.0
2015-04-27T07:45:29.767Z
2015-04-29T23:06:04.743Z
2015-04-29T23:06:04.743Z
Joe Bebel
<p>You can find two different proofs in:</p>

<p><a href="https://www.cs.auckland.ac.nz/research/groups/CDMTCS/researchreports/008HHP.pdf" rel="noreferrer">Gregory J. Chaitin, Asat Arslanov, Cristian Calude: Program-size Complexity Computes the Halting Problem. Bulletin of the EATCS 57 (1995)</a></p>

<p>In <a href="http://http//www.springer.com/us/book/9780387339986" rel="noreferrer">Li, Ming, Vitányi, Paul M.B.; An Introduction to Kolmogorov Complexity and Its Applications</a> 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).</p>

<p>** I decided to publish an <a href="http://www.nearly42.org/cstheory/halting_to_kolmogorov/" rel="noreferrer">extended version of it on my blog</a>.</p>

CC BY-SA 3.0
2015-05-01T06:04:17.790Z
Are these proofs are really Turning reductions (one to one (or) one to many) ?

I am confused !! please help me
Krishna Chikkala
CC BY-SA 3.0
2015-05-01T17:07:46.457Z
@KrishnaChikkala: the first is surely a [Turing reduction](http://en.wikipedia.org/wiki/Turing_reduction). I found it not so clear, so I decided to [publish an extended version of it on my blog](http://www.nearly42.org/cstheory/halting_to_kolmogorov/). 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
CC BY-SA 3.0
2015-04-28T10:18:16.003Z
2015-05-06T08:15:49.850Z
2015-05-06T08:15:49.850Z
Marzio De Biasi
<p>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. </p>

<computability><reductions><kolmogorov-complexity>
Proof for Kolmogorov complexity is uncomputable using reductions
Krishna Chikkala
# Proof for Kolmogorov complexity is uncomputable using reductions

(Asked by: username_0 on 2015-04-26)

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.

**Tags:** computability, reductions, kolmogorov-complexity

---

## 2 answers

### Answer by username_3 on 2015-04-28. Score: 12 | Accepted answer

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)](https://www.cs.auckland.ac.nz/research/groups/CDMTCS/researchreports/008HHP.pdf)

In [Li, Ming, Vitányi, Paul M.B.; An Introduction to Kolmogorov Complexity and Its Applications](http://http//www.springer.com/us/book/9780387339986) 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](http://www.nearly42.org/cstheory/halting_to_kolmogorov/).

> **Comments:**
> **username_0**: Are these proofs are really Turning reductions (one to one (or) one to many) ?  I am confused !! please help me  
> **username_3**: @KrishnaChikkala: the first is surely a [Turing reduction](http://en.wikipedia.org/wiki/Turing_reduction). I found it not so clear, so I decided to [publish an extended version of it on my blog](http://www.nearly42.org/cstheory/halting_to_kolmogorov/). 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.  

---

### Answer by username_1 on 2015-04-27. Score: 7

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.

> **Comments:**
> **username_2**: But what about a Turing reduction?  
> **username_1**: 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.  
> **username_1**: Actually I retract that $R$ can be used in that way. It is not so clear in the Turing reduction context.  
> **username_2**: A few places claim that Kolmogorov complexity is Turing equivalent to the Halting problem, for example Miltersen's notes http://www.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.  

---

