First problem

If $M$ is a Turing machine, then we say that the length of the description of $\langle$M$\rangle$ of M is the number of symbols in the string describing M. We say that M is minimal if there is no Turing machine equivalent to M that has a shorter description. We let

$MIN_{TM}$={$\langle$M$\rangle$|M is a minimal TM}

Claim: $MIN_{TM}$ is not recursively enumerable.

Proof (by Sipser):

$C$="On input $w$:

  1. Obtain, via the recursion theorem, own description $\langle$C$\rangle$
  2. Run the enumerator $E$ until a machine $D$ appears with a longer description than that of C.
  3. Simulate $D$ on input $w$".

I am trying to understand the proof above. Since $MIN_{TM}$ is infinite, why does it follow that $E$'s list must contain a TM with a longer description than $C$'s description and is also equivalent to C?

Since it follows that $E$'s list must contain a TM with a longer description than $C$'s description, then step $2$ of $C$ must eventually terminate with some TM $D$ that is longer than $C$. Then, $C$ simulates $D$, and is equivalent to it. Since $C$ is shorter than $D$ and is equivalent to it, $D$ cannot be minimal. But $D$ appears on the list that $E$ produces, thus a contradiction.

Second problem

Let $x$ be a binary string. We say that the minimal description of $x$, written as $d(x)$, is the shortest string $\langle$M, w$\rangle$ where TM $M$ on input $w$ halts with $x$ on its tape. So, the Kolmogorov-Chaitin complexity $K(x)$ is written as, $$K(x)=|d(x)|.$$ $K(x)$ is defined to be the length of minimal description of $x$.

How can you prove that $K(x)$ is uncomputable?

The proofs I read on Wikipedia and other sites are proofs that involve programming arguments. I am not a computer scientist nor do I have any knowledge in programming (just a math student). I would like to see a cohesive (but simple) mathematics proof.

I read that the decidability of Kolmogrovo-Chaitin complexity would imply that the halting problem is decidable, how?

  • $\begingroup$ Notice that the given proof actually shows that $MIN_{TM}$ contains no infinite c.e. set; i.e. that $MIN_{TM}$ is immune. $\endgroup$ – Quinn Culver Jun 5 '11 at 4:28
  • $\begingroup$ en.wikipedia.org/wiki/Berry_paradox has a simple explanation of this. $\endgroup$ – Dan Brumleve Jun 5 '11 at 19:29

Diagonalization is a difficult concept that is hard to grasp. All the proofs you mention in your question are proofs via diagonalization. These are proofs by contradiction - suppose X were true, then you can do Y, and reach a contradiction; so X must be false.

A good example is the first proof that you mention (your first question). There are plainly infinitely many minimal TMs (since TMs can generate every finite string). So in particular, the enumerator E eventually outputs some machine D whose complexity is larger than C.

We reach a contradiction since C generates the same output as D. This contradiction that you're having troubles with, stems for the fact that there is no procedure that enumerates minimal TMs, which is what we set out to prove in the first place.

The difficult part here is using the recursion theorem. I trust that it's explained well by Sipser, but you can also check out the Wikipedia article or countless other web (and paper) resources.

The proof of uncomputability of Kolmogorov complexity is almost the same. While the version on Wikipedia does contain pseudocode, it's pretty simple. More importantly, it constitutes a "mathematical proof". The proof could be rewritten in paragraph format just as well. Some people find it easier if it's presented as pseudocode. Here is a paragraph version.

Suppose Kolmogorov complexity were computable. One could then write a program that enumerates all strings and outputs a string $s$ of complexity at least $n_0$, where $n_0$ is some constant we choose later. The program has size $C + 2\log n_0$ for some constant $C$ depending on the particular encoding, and so $$ C + 2\log n_0 \geq K(s) \geq n_0. $$ For large enough $n_0$, this is contradictory.


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.