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.