i was asked to determine if its in RE and if its in co-RE. well i think its easy to say the language is not in RE but i was wondering if this language is in co-RE. so the question is if $\overline{L}$= {< 𝑀1 >, < 𝑀2 >: $\ 𝐿(𝑀1 )\not\subseteq\ 𝐿(𝑀2)$} is in RE? my intuition is that if there is a word in 𝐿(𝑀1 ) which is not in 𝐿(𝑀2 ), we can eventually get to this word and try to run it on both machines.

  • $\begingroup$ Since $\bar L$ includes any string that is not in $L$, it includes the string $\langle M1 \rangle$ so your definition of $\bar L$ is not correct. What you could do is prove that $L \notin R$ and $L \in RE$ which would mean that $\bar L \notin RE$ and hence $L \notin$ co-RE $\endgroup$ – user137481 Jan 15 at 23:34

Your Answer

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

Browse other questions tagged or ask your own question.