Let $$R = \{\langle M \rangle \mid L(M) \text{ is decidable}\}.$$ Is $R$ recursively enumerable or co-recursively enumerable?

  • 1
    $\begingroup$ What did you try? This might be a job for the Rice-Shapiro theorem, or some careful m-reductions. $\endgroup$
    – chi
    Mar 29, 2017 at 12:53
  • 1
    $\begingroup$ What did you try? Where did you get stuck? The answer to this question seems to be immediate from material that you've almost certainly been taught. We're happy to help with conceptual questions but just solving homework-style exercises for you is unlikely to really help you. $\endgroup$ Mar 29, 2017 at 13:50
  • $\begingroup$ A language $L$ is decidable if $L = L(M)$ for some Turing machine $M$. Does this help? $\endgroup$ Mar 29, 2017 at 16:33
  • 1
    $\begingroup$ A language $L$ is recognizable if and only if there is a TM $M$ for which $L=L(M)$. There are languages (like the acceptance language $A_{TM}$) which are not decidable but are recognizable. $\endgroup$ Mar 30, 2017 at 17:01
  • 2
    $\begingroup$ @kanjim What is the definition of $L(M)$ that you use? $\endgroup$ Mar 30, 2017 at 17:23

1 Answer 1


This set is not r.e. nor co-r.e., in fact it's complete at the 3rd level of the arithmetic hierarchy ($\Sigma^0_3$-complete). This is shown in Soare's textbook.


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.