9
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Furthermore, Chaitin's proof (in that link) shows that the oracle queries can be made in parallel. $\;\;\;\;$ $\endgroup$ – user6973 Apr 30 '15 at 1:07
  • $\begingroup$ Are these proofs are really Turning reductions (one to one (or) one to many) ? I am confused !! please help me $\endgroup$ – Krishna Chikkala May 1 '15 at 6:04
  • $\begingroup$ @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. $\endgroup$ – Marzio De Biasi May 1 '15 at 17:07
7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ But what about a Turing reduction? $\endgroup$ – Sasho Nikolov Apr 27 '15 at 8:05
  • $\begingroup$ 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. $\endgroup$ – Joe Bebel Apr 27 '15 at 8:16
  • $\begingroup$ Actually I retract that $R$ can be used in that way. It is not so clear in the Turing reduction context. $\endgroup$ – Joe Bebel Apr 27 '15 at 9:41
  • 3
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Apr 27 '15 at 17:16
  • $\begingroup$ $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$. $\endgroup$ – user30585 Apr 29 '15 at 21:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.