Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This thread can be broken up into two questions.

First I am trying to understand the proof that $MIN_{TM}$ is not recursively enumerable.

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}$={$\langle$M$\rangle$|M is a minimal TM} is not R.E.

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. Stimulate D on input w".

Question: 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 stimulates 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 question:

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.

Question: 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?

share|cite|improve this question
Notice that the given proof actually shows that $MIN_{TM}$ contains no infinite c.e. set; i.e. that $MIN_{TM}$ is immune. – Quinn Culver Jun 5 '11 at 4:28 has a simple explanation of this. – Dan Brumleve Jun 5 '11 at 19:29
up vote 3 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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