0
$\begingroup$

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.
$\endgroup$
4
  • $\begingroup$ Not off topic, but maybe better suited for cs.SE. $\endgroup$ Commented Dec 8, 2023 at 16:31
  • $\begingroup$ I've edited your question to use mathjax (which is searchable) rather than an image (which isn't) so that other users have an easier time finding this question ^_^. (I know you said you would change it, but it didn't take so long to do it myself. In the future we tend to prefer mathjax to images here for searchability and formatting, though) $\endgroup$ Commented Dec 8, 2023 at 16:33
  • $\begingroup$ @GiorgosGiapitzakis The MSE community is just so much better. $\endgroup$ Commented Dec 8, 2023 at 17:25
  • $\begingroup$ Thanks! @HallaSurvivor $\endgroup$ Commented Dec 8, 2023 at 17:25

1 Answer 1

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

$\endgroup$
3
  • $\begingroup$ Ahhhh, ok I get it. So this argument is essentially the same for every non-trivial property of a TM's language, and that is precisely why the generalization of Rice's Theorem is useful (?) $\endgroup$ Commented Dec 8, 2023 at 17:26
  • $\begingroup$ I think it's Rice's theorem itself, not it's generalization. But yes, we just transform halting scenarios to some machine in $L$, and non-halting scenarios to some machine not in $L$. $\endgroup$
    – mihaild
    Commented Dec 8, 2023 at 17:52
  • $\begingroup$ Yes, I meant "this generalization which is Rice's Theorem." Thank you so much for your answer. Helped me understand better! $\endgroup$ Commented Dec 8, 2023 at 17:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .