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$:
- Produce a TM $M_x$ which works as follows (note this TM is never actually run):
$M_x$ = "On input $x$:
- Ignore input $x$
- Simulate $M$ on input $w$. If $M$ halts, then $M_x$ accepts $x$. Otherwise, $M$ does not halt and neither does $M_x$"
- 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:
- 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…
- 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?
- The "on input $x$" seems arbitrary to me; it feels like we are just waving our hands.
Best Answer
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$.
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.
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$.