Is the language A decidable? [closed]

Question

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 .

Answer 1

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.