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$– chiMar 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$– David RicherbyMar 29, 2017 at 13:50
-
$\begingroup$ A language $L$ is decidable if $L = L(M)$ for some Turing machine $M$. Does this help? $\endgroup$– Yuval FilmusMar 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$– Rick DeckerMar 30, 2017 at 17:01
-
2$\begingroup$ @kanjim What is the definition of $L(M)$ that you use? $\endgroup$– Yuval FilmusMar 30, 2017 at 17:23
|
Show 1 more comment
1 Answer
$\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.
answered Oct 1, 2018 at 6:12