Turing Machine equivalence in MinTM proof
-
05-11-2019 - |
题
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$:
- 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$."
$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:
- How do we know that $MIN_{\mathrm{TM}}$ is inifinite?
- Why $C$ is equivalent to $D$?
- 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.
- Equivalence is based only on ability to construct same language recognizers or to say $L(M_1) = L(M_2)$
没有正确的解决方案
不隶属于 cs.stackexchange