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

  • 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
    Commented 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$ Commented Jul 16, 2020 at 1:38
  • $\begingroup$ @muttiganaceoys: Not so. They have been proveably shown to be undecidable. $\endgroup$ Commented 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$
    – dshrikant
    Commented Jul 16, 2020 at 10:31

1 Answer 1


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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.