0
$\begingroup$

$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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David Richerby Nov 8 '18 at 20:57
  • $\begingroup$ If there is some specific part of the proof you want to ask about, a more specific question might be appropriate. $\endgroup$ – David Richerby Nov 8 '18 at 20:57
1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What is co-c.e? $\endgroup$ – pureundergrad Nov 8 '18 at 19:10
  • 1
    $\begingroup$ Being the complement of a computably enumerable (hence recognizable) language. $\endgroup$ – Arno Nov 8 '18 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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