Error in proof of decidability

Question

$L=\{\left<M\right> \ | \ M $ is a TM s.t. $M$ does not accept any string starting with a '1' $\}$. Assume the alphabet to be $\Sigma = \{0,1\}$.

By Rice's theorem $L$ is undecidable. I managed to "prove" that $L$ is decidable. So can someone point out the error in my proof. To keep things clean I ignore the empty string since it can easily be dealt with as a special case.

We can write $$L = \{\left<M\right> \ | \ w\in \Sigma^*, \ w \in L(M) \implies w[0] \neq 1\}$$ $$ = \{\left<M\right> \ | \ w\in \Sigma^*, \ w \in L(M) \implies w[0] = 0 \}$$ To get $\overline{L}$ we need to negate the condition in $L$. Hence $$\overline{L}= \{\left<M\right> \ | \ w\in \Sigma^*, \ w \in L(M) \implies w[0] = 1 \}$$

We have $$\exists \ w\in \Sigma^* \text{ such that } w\in L(M) \text{ and } w[0] = 1 \iff \left<M\right>\not \in L \iff \left<M\right> \in \overline{L}$$ We can construct a recognizer for $\overline{L}$ by searching for such a $w$

$R=$ 'on input $\left<M\right>$ where $M$ is a valid TM:

1. for $w \in \Sigma^*$:

2. $\ \ $if $M(w) =$ accept

3. $\ \ \ \ $if $w[0]=1$ then accept'

So $\overline{L}$ is recognizable. Similarly we have

$$\exists \ w\in \Sigma^* \text{ such that } w\in L(M) \text{ and } w[0] = 0 \iff \left<M\right>\not \in \overline{L} \iff \left<M\right> \in L$$ We can construct a recognizer for $L$ by searching for such a $w$

$R'=$ 'on input $\left<M\right>$ where $M$ is a valid TM:

1. for $w \in \Sigma^*$:

2. $\ \ $if $M(w) =$ accept

3. $\ \ \ \ $if $w[0]=0$ then accept'

So $L$ is also recognizable, this means $L$ is decidable.

Answer 1

The error is in the definition of $\overline{L}$. It should be $$ \overline{L} = \{ \langle M \rangle \mid \exists w \, w \in L(M) \land w[0] = 1 \}. $$ In other words, $\overline{L}$ consists of all Turing machines which do accept some string starting with 1.

(More pedantically, $\overline{L}$ also accepts all strings which aren't descriptions of Turing machines.)

One further note: $w[0] \neq 1$ is not the same as $w[0] = 0$, since $w$ could also be the empty string.

Answer 2

Your language is indeed co-c.e.; the mistake is in the argument claiming recognizability of $L$. You have the existential and universal quantifier mixed up.