Let $$R = \{\langle M \rangle \mid L(M) \text{ is decidable}\}.$$ Is $R$ recursively enumerable or co-recursively enumerable?
$\begingroup$
$\endgroup$
6
-
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
|
Show 1 more comment
$\begingroup$
$\endgroup$
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.
