1
$\begingroup$

Is the language $A$ decidable ? Please help me get the proof right !!

$A = \{ \langle M \rangle | M \text{ is } TM \text{ such that } L(M) \neq \Sigma^* \}$

My proof is by contradiction. Assume $A$ is decidable and let $R$ be decider for it. I will construct decider $S$ for $A_{tm}$, using $R$ as a subroutine.

S = on input <M,w>
constructs M_w = on input x
 if x!=w accept
 else run M on w
  if M accepts => accept
  else => reject
run R on M_w 
 if R accepts => reject
 if R rejects => accept

Note : If $M$ accepts $w$ then $L(M_w) = \Sigma^*$ , then $R$ ran on $M_w$ will reject it, and $S$ will accept. If $M$ rejects or loops on $w$, $L(M_w) \neq \Sigma^*$, then $R$ ran on $M_w$ will accept, and $S$ will reject. Therefore, we created a decider for $A_{tm}$, but we know that $A_{tm}$ is undecidable, our assumption was wrong => $A$ is undecidable .

$\endgroup$

closed as unclear what you're asking by David Richerby, Yuval Filmus, Evil, Rick Decker, Juho Aug 30 '17 at 8:56

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ What is $A_{tm}$ (A_tm)? $\endgroup$ – fade2black Aug 11 '17 at 18:09
  • $\begingroup$ A_tm = { <M,w> | M is a TM and M accepts w } $\endgroup$ – acagu Aug 11 '17 at 18:33
  • $\begingroup$ Do you have any specific doubt about the veracity of your solution? $\endgroup$ – Yuval Filmus Aug 11 '17 at 20:19
  • 1
    $\begingroup$ Your question already includes a complete answer to the original problem but no question about this answer. Thus, only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. $\endgroup$ – David Richerby Aug 11 '17 at 21:02
0
$\begingroup$

I don't understand how you call $R$ from $S$. The following is a possible solution.

Let's reduce $A_{TM}$ (halting problem) to $\overline{A} = \{ \langle M \rangle | M \text{ is } TM \text{ such that } L(M) = \Sigma^* \}$ instead of $A$, since decidability of $\overline{A}$ would imply decidability of $A$.

First note that $M_\emptyset (\text{ TM accepting nothing )} \notin$ $\overline{A}$ and it is clearly that $\overline{A}$ is not empty since a TM machine simply accepting any string is in $\overline{A}$, so let's choose $M_1$ from the set $\overline{A}$ and let $L_1$ be the language recognizable by $M_1$.

For any $\langle M, w \rangle$ construct a new TM $M'$

  M'(x)
   Simulate M on w
   If M accepts w then run M_1 on x
   If M_1 accepts x then ACCEPT

Now let's show the reduction:
$\langle M,w \rangle \in A_{TM} \Rightarrow M \text{ accepts } w \Rightarrow M'$ accepts $x$ exactly when $M_1$ accepts $x \Rightarrow L(M') = L_1$ which implies $\langle M_1 \rangle \in \overline{A}$. So we have obtained

$$\langle M,w \rangle \in A_{TM} \Rightarrow \langle M' \rangle \in \overline{A}$$

Similarly, $\langle M,w \rangle \notin A_{TM} \Rightarrow M \text{ does not accepts } w \Rightarrow M' \text{ accepts no string } \Rightarrow L(M') = \emptyset $ which implies $\langle M' \rangle \notin \overline{A}$. So we have obtained $$\langle M,w \rangle \notin A_{TM} \Rightarrow \langle M' \rangle \notin \overline{A}$$

Now if $\overline{A}$ were decidable then on any input $\langle M, w \rangle$ we could construct $M'$ as above and decide if $M$ halts on $w$ by checking $\langle M' \rangle \in \overline{A}$.

Finally, the general case of the proof above is known as the Rice's theorem, which you could apply directly to prove that $A$ is not decidable.

$\endgroup$

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