Computer Science – Understanding Proof of Undecidability for $L = \{ \langle M \rangle \mid M \text{ is a TM that accepts the input string } 101\}$

computabilitycomputer sciencedecidabilityturing-machines

I understand of the existence of Rice's Theorem, however, I want to understand better how this reduction is formed. My professor gives the answer as follows:

"By contradiction, assume that $L$ is decidable and let $D$ be a decider for $L$. Then construct the TM $S$ such that $S$ decides the Halting Problem as follows:

S = "On input $\langle M, w \rangle$:

  1. Produce a TM $M_x$ which works as follows (note this TM is never actually run):

$M_x$ = "On input $x$:

  1. Ignore input $x$
  2. Simulate $M$ on input $w$. If $M$ halts, then $M_x$ accepts $x$. Otherwise, $M$ does not halt and neither does $M_x$"
  1. Run $D$ on $\langle M_x \rangle$ and accept if $D$ accepts $\langle M_x \rangle$ and reject if $D$ rejects $\langle M_x \rangle$."

My questions/concerns:

  1. How exactly does the construction of $S$ relate to the original language $L$? I am having a hard time seeing how we are actually deciding the Halting Problem…
  2. The construction of $M_x$ says "If $M$ halts, then $M_x$ accepts $x$." This seems like circular reasoning or a contradiction in and of itself. How can we say "If $M$ halts…" when the question of a TM halting is undecidable?
  3. The "on input $x$" seems arbitrary to me; it feels like we are just waving our hands.

Best Answer

  1. Note that $M_x$ either accepts all words (if $M$ halts on $w$), or accepts none (if $M$ doesn't halt on $w$). So, $\langle M_x \rangle \in L$ iff $M$ halts on $w$.

  2. We don't ask for solution of halting problem. $M_x$ just runs $M$ on input $w$, waits until it finishes (forever if it doesn't), and then declares that it accepts input.

  3. I think it's a bit poor choice of notation, it would be better to say that TM $M_w$ on input $x$ ignores $x$ and launches $M$ on input $w$, and we launch $D$ on $\langle M_w\rangle$.

Related Question