Knowing that all Recursive languanges are Decidable and All Not R.E. Languages are Undecidable (correct me if I am wrong), Are all languages which are R.E. but not Recursive also Undecidable?
R.E. ==> Recursively Enumerable
4
-
5$\begingroup$ Recursive == Decidable. They mean the same thing. So if you ask if "Are languages (of any category) which are not Recursive, also Undecidable?" the answer is "yes, definitionally" $\endgroup$– JakeCommented Jul 16, 2020 at 0:52
-
1$\begingroup$ Nonrecursive recursively enumerable languages are undecidable by definition. These languages are those which are guaranteed to stop if the answer is yes. $\endgroup$– ṂųỻịgǻňạcểơửṩCommented Jul 16, 2020 at 1:38
-
$\begingroup$ @muttiganaceoys: Not so. They have been proveably shown to be undecidable. $\endgroup$– Mozibur UllahCommented Jul 16, 2020 at 2:58
-
$\begingroup$ By definition every language which is not Decidable is Undecidable, but in case of Recursively Enumerable languages there is some portion of it which is partially Decidable (strings which belong to the language). This sums it up, thanx @muttiganaceoys, Jake $\endgroup$– dshrikantCommented Jul 16, 2020 at 10:31
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
A language is recursive (newer terminology: computable, also decidable) is there is a Turing machine that always halts that recognizes the language. It is recursively enumerable (new: computably enumerable) if there is a Turing machine that accepts it (it halts and accepts for strings in the language, it might never halt for strings not in the language). If the language is not recursive, it isn't decidable ("recursive" and "decidable" are alternative terms for the same class of languages).
