# Error in proof of decidability

$$L=\{\left \ | \ 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 \ | \ w\in \Sigma^*, \ w \in L(M) \implies w \neq 1\}$$ $$= \{\left \ | \ w\in \Sigma^*, \ w \in L(M) \implies w = 0 \}$$ To get $$\overline{L}$$ we need to negate the condition in $$L$$. Hence $$\overline{L}= \{\left \ | \ w\in \Sigma^*, \ w \in L(M) \implies w = 1 \}$$

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

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

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

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

3. $$\ \ \ \$$if $$w=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 \iff \left\not \in \overline{L} \iff \left \in L$$ We can construct a recognizer for $$L$$ by searching for such a $$w$$

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

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

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

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

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

• Sorry but "please check my work" questions are off-topic here. Except in rare cases where the error is common and/or instructive, it's very unlikely that anyone else will ever make the same mistake again. We prefer to spend our time in a way that will help as many people as possible, and questions that will never be interesting to anyone else don't do that. – David Richerby Nov 8 '18 at 20:57
• If there is some specific part of the proof you want to ask about, a more specific question might be appropriate. – David Richerby Nov 8 '18 at 20:57

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 = 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 \neq 1$$ is not the same as $$w = 0$$, since $$w$$ could also be the empty string.
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.