Question

The proof with contradiction that $MIN_{\mathrm{TM}}$ is not Turing-recognizable from Michael Sipser's textbook "Introduction to the Theory of Computation" (Theorem 6.7) is as follows:

$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$."

$MIN_{\mathrm{TM}}$ is infinite, so at least one $D$ occurence will be observed.

Because $C$ is shorter than $D$ and is equivalent to it, $D$ cannot be minimal.

I would like to understand three things from this proof:

  1. How do we know that $MIN_{\mathrm{TM}}$ is inifinite?
  2. Why $C$ is equivalent to $D$?
  3. Why "Because $C$ is shorter than $D$ and is equivalent to it, $D$ cannot be minimal"?. Why do we expect $D$ to be minimal?

Edit : I have some opinions (I want to verify) about my questions. Please correct me If I am wrong.

  1. Equivalence is based only on ability to construct same language recognizers or to say $L(M_1) = L(M_2)$

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top