2
$\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: enter image description here

(I gave a picture instead of typing since he uses a special $\LaTeX$ environment, if I need to change this please let me know.)

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$
2
  • 1
    $\begingroup$ Please ask only one question per post. I don't understand what "How exactly does ... relate to ..." is supposed to be answered. It sounds like we'd have to read your mind to guess what kind of answer you are hoping for. Do you want to ask "Why does $S$ decide the halting problem?" If so, you might start by writing down the definition of what it means to decide the halting problem, what are each of the conditions, and then see if you can check whether those are met. We're looking to build up an archive of knowledge that will be useful to others in the future. $\endgroup$
    – D.W.
    Commented Dec 8, 2023 at 20:32
  • 1
    $\begingroup$ Please don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. You can use LaTeX. $\endgroup$
    – D.W.
    Commented Dec 8, 2023 at 20:32

2 Answers 2

1
$\begingroup$

As you know, a Turing reduction from $L_1$ to $L_2$ (i.e. $L_1 \leq_T L_2$) means that if we can decide $L_2$, then we can also decide $L_1$. In general to show $L_1 \leq_T L_2$, we construct a machine $T$ such that $T$ decides $L_1$ and $T$ is permitted to query $L_2$. Being permitted to query $L_2$ means that $\forall w \in \Sigma^*$, $T$ can determine if $w \in L_2$ or $w \notin L_2$ (while $T$ is running) by asking an "oracle" whether or not $w$ is in $L_2$. Understanding how querying a language is accomplished on the tape is not necessary for understanding the reduction at a high level, but I would encourage you to look into it.

In your case, we're showing that $HALT_{TM} \leq_T L$ by constructing the machine $S$ such that $S$ decides $HALT_{TM}$ and $S$ is permitted to query $L$. This is how $S$ relates to $L$: $S$ queries $L$ (i.e. $S$ asks whether or not a string is in $L$, specifically in step $2$ of the provided pseudocode). An oracle is not a Turing machine, but a decider can be used to simulate an oracle because all questions about whether or not a string $w$ is in a given language can be answered by simply running the decider for that language on $w$. So in $S$, the decider, $D$, for $L$ is playing the role of the oracle (more specifically, $D$ is how $S$ queries $L$).

Now we just need to show that $S$ decides $HALT_{TM}$. $S$ takes in input $\langle M, w \rangle \in \Sigma^*$, which we understand to be the code of the machine $M$ and a string $w$. Recall that $S$ must determine whether or not $M$ halts on $w$.

$S$ starts by constructing a machine $M_x$. You stated that "on input $x$" in the definition of $M_x$ seems arbitrary and that's because it is. We're defining the behavior of $M_x$ when taking in any input $x \in \Sigma^*$. What's probably a little confusing is that $x$ is being used to denote the variable input string and in the name of the machine ($M_x$) but these have no relation. To address your second question regarding the condition "if $M$ halts on $w$", I will note that we are not deciding if $M$ halts on $w$ or not. $M_x$ is running/simulating $M$ on $w$, and if $M$ happens to halt on $w$ while $M_x$ is running $M$ on $w$, then $M_x$ behaves accordingly as described in the pseudocode. This seems reasonable as $HALT_{TM}$ is recognizable. If $M$ does not halt on $w$, then $M_x$ will not halt either because it will run $M$ on $w$ and wait for $M$ to halt on $w$ forever. It's important to note that $M_x$ is not determining that $M$ does not halt on $w$ and not halting in response to this but rather $M_x$ is not halting because it is running $M$ on $w$ until $M$ halts on $w$, however, $M$ never halts on $w$. We will now briefly prove the following lemma:

Lemma: If $\langle M, w \rangle \in HALT_{TM}$, then $M_x$ accepts all input strings (including $101$), and if $\langle M, w \rangle \notin HALT_{TM}$, then $M_x$ does not halt on any input strings and therefore does not accept any input strings (including $101$).

Consider $x \in \Sigma^*$. First suppose $\langle M, w \rangle \in HALT_{TM}$. Since $M$ halts on $w$, $M_x$ accepts $x$ by the definition of $M_x$. Moreover, because $M_x$ does the same thing, regardless of its input, we know that $M_x$ accepts all inputs. Now suppose $\langle M, w \rangle \notin HALT_{TM}$. Since $M_x$ runs $M$ on $w$ until $M$ halts on $w$ and we've assumed $M$ never halts on $w$, $M_x$ runs forever/does not halt and therefore does not accept $x$. Once again, since $M_x$ always runs $M$ on $w$, regardless of its input, we know that $M_x$ does not halt on all inputs and therefore does not accept any inputs.

With this in mind, we can now show that $S$ decides $HALT_{TM}$. Consider the following two cases:

  1. $\langle M, w \rangle \in HALT_{TM}$. By our lemma, $M_x$ accepts all input strings (including $101$), which means $\langle M_x \rangle \in L$. Since $D$ decides $L$, $D$ accepts $\langle M_x \rangle$, so by step $2$ of the pseudocode, $S$ accepts $\langle M, w \rangle$.

  2. $\langle M, w \rangle \notin HALT_{TM}$. By our lemma, $M_x$ does not halt on any input strings and does not accept any input strings (including $101$), which means $\langle M_x \rangle \notin L$. Since $D$ decides $L$, $D$ rejects $\langle M_x \rangle$, so by step $2$ of the pseudocode, $S$ rejects $\langle M, w \rangle$.

Thus, if $\langle M, w \rangle \in HALT_{TM}$ then $S$ accepts $\langle M, w \rangle$, and if $\langle M, w \rangle \notin HALT_{TM}$, then $S$ rejects $\langle M, w \rangle$. Putting these together, we have that $S$ decides $HALT_{TM}$ and $HALT_{TM} \leq_T L$. Thus, if $L$ is decidable, then $HALT_{TM}$ would be decidable.

$\endgroup$
1
$\begingroup$
  1. Fix $\langle M, w\rangle$, and consider the constructed machine $M_x$. It is not hard to see by the construction of $M_x$ that either $M_x$ accepts all its inputs (and that happens when $M$ halts on $w$), or $M_x$ does not halt on all its inputs (and that happens when $M$ does not halt on $w$). So $M_x$ behaves on all its inputs the same way, depending on what happens in the run of $M$ on $w$. Hence, to understand how $M_x$ behaves, it is sufficient to consider its behaviour on the input $101$, but we can do that through the decider machine $D$. Thats why we have the check in item 2, and the magic here is that $D$ halts on $\langle M_x \rangle$ as it is a decider TM, and therefore, $S$ is also a decider. So in total we get that, $D$ accepts $\langle M_x \rangle$ iff $M_x$ accepts the input $ 101$ iff $M_x$ accepts all its input (as $M_x$ behaves the same on all inputs) iff $M$ halts on $w$ (by the construction of $M_x$). So we got in total that $S$ decides the halting problem.

Note: The machine $S$ never simulates the run of $M$ on $w$, it produces a description of a machine $M_x$ that does that, and then simulates the run of $D$ on $\langle M_x\rangle$ and halts.

  1. Note that if $M$ does not halt on $w$, then $M_x$ does not halt as well. So $M_x$ is not deciding the halting problem, it just simulates the run of $M$ on $w$ and waits for $M$ to accept $w$, and in fact it can wait forever and not halt at all. So its not a contradiction as we are here kinda semi-deciding the halting problem and not deciding it.

  2. Its not arbitrary, its how $M_x$ works. It does the same thing regardless of the input $x$, and so we can write "on input $x$, do blah blah blah" -- meaning on any input $x$, we behave the same way.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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