Error in proof of decidability $L=\{\left&lt;M\right&gt; \ | \ 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&lt;M\right&gt; \ | \ w\in \Sigma^*, \ w \in L(M) \implies w[0] \neq 1\}$$
$$ = \{\left&lt;M\right&gt; \ | \ 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&lt;M\right&gt; \ | \ 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&lt;M\right&gt;\not \in L \iff \left&lt;M\right&gt; \in \overline{L}$$
We can construct a recognizer for $\overline{L}$ by searching for such a $w$

$R=$ 'on input $\left&lt;M\right&gt;$ where $M$ is a valid TM:


for $w \in \Sigma^*$:
$\ \ $if $M(w) =$ accept
$\ \ \ \ $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&lt;M\right&gt;\not \in \overline{L} \iff \left&lt;M\right&gt; \in L$$
We can construct a recognizer for $L$ by searching for such a $w$

$R'=$ 'on input $\left&lt;M\right&gt;$ where $M$ is a valid TM:


for $w \in \Sigma^*$:
$\ \ $if $M(w) =$ accept
$\ \ \ \ $if $w[0]=0$ then accept'


So $L$ is also recognizable, this means $L$ is decidable.
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.