2
$\begingroup$

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)$
$\endgroup$
1
$\begingroup$

How do we know that $MIN_{\mathrm{TM}}$ is inifinite?

There are infinitely many partial recursive functions (i.e., functions which are computed by TMs) and to each such function there is at least one TM which computes it and has minimal description.

Why $C$ is equivalent to $D$?

Because of point 3., which essentially forces $C$ and $D$ to have the same behavior. In this case, yes, equivalence is used in the sense that $L(C) = L(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?

$D$ is minimal because $\langle D \rangle \in MIN_{\textrm{TM}}$. Recall that, by assumption, the enumerator $E$ only outputs descriptions in $MIN_{\textrm{TM}}$. The point is that $\langle C \rangle$ is fixed (because we have just provided a description for it), but $E$ gives us descriptions of TMs of arbitrary length indefinitely; hence, $E$ will eventually output some description which is longer than $\langle C \rangle$.

$\endgroup$
  • $\begingroup$ That makes sense, especially that <D> is supposed to be minimal being printed by MinTM enumerator. Thanks. $\endgroup$ – Prithi Jul 5 at 23:24
  • $\begingroup$ @Prithi Glad to be of help. If you believe this answers your question, don't forget to click the tick mark on the left and mark it as an "accepted" answer :) $\endgroup$ – dkaeae Jul 6 at 7:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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