3
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • 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 '17 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$ – David Richerby Mar 29 '17 at 13:50
  • $\begingroup$ A language $L$ is decidable if $L = L(M)$ for some Turing machine $M$. Does this help? $\endgroup$ – Yuval Filmus Mar 29 '17 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$ – Rick Decker Mar 30 '17 at 17:01
  • 2
    $\begingroup$ @kanjim What is the definition of $L(M)$ that you use? $\endgroup$ – Yuval Filmus Mar 30 '17 at 17:23
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

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.