# Minimal Turing machines are not recursively enumerable & Kolmogorov complexity is uncomputable

### 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?

• 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
• en.wikipedia.org/wiki/Berry_paradox has a simple explanation of this. – Dan Brumleve Jun 5 '11 at 19:29

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.