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$:
- Obtain, via the recursion theorem, own description $\langle$C$\rangle$
- Run the enumerator $E$ until a machine $D$ appears with a longer description than that of C.
- 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?