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$ – Jake Jul 16 '20 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ểơửṩ Jul 16 '20 at 1:38
-
$\begingroup$ @muttiganaceoys: Not so. They have been proveably shown to be undecidable. $\endgroup$ – Mozibur Ullah Jul 16 '20 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$ – dshri Jul 16 '20 at 10:31
Add a comment
|
$\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).
