1
$\begingroup$

I learned that recursive language are decidable; correct me if I am wrong. However, I have found some arguments that seem to contradict this. These may or may not be correct; please let me know.

If a language is an REL (recursive enumerable language), I know that there exists a TM (Turing machine) that accepts it (regardless of the TM halting or not). Say, however, that for a language $L$ you have found a TM which accepts it, thus indicating $L$ is REL. We know that, given a TM, it is undecidable whether the TM halts or not. Thus, it is not possible to deduce whether $L$ is recursive or not: we have a TM that accepts $L$, but whether the TM halts or not is undecidable and, thus, we cannot comment on whether $L$ is recursive or not; this makes telling whether $L$ is recursive or not undecidable. Hence, recursive languages should be undecidable―which they are not!

What is wrong with the above reasoning?

$\endgroup$
  • 2
    $\begingroup$ "Recursive" and "decidable" mean exactly the same thing. $\endgroup$ – David Richerby Dec 31 '18 at 22:03
3
$\begingroup$

You are correct. The problem of deciding "$L$ is a recursively enumerable language" is undecidable. However, that does not make $L$ itself undecidable.

Do not mistake a language for its class! Telling whether $L$ is in a class is definitely not the same as deciding membership in $L$.

$\endgroup$
  • $\begingroup$ i still dont understand why REL are undecidable ?. given a language we can decide whether the language is decidable that the language is REL by making a TM but we cannnot deduce that the language is recursive or REL-but not recursive which makes them undecidable. also everybody knows that the memebership for recursive is decidable $\endgroup$ – Noob Dec 25 '18 at 12:12
  • $\begingroup$ tell me one thing , that when we say that recursive language are decidable ,are we talking about the memebership problem of the language or are we concerned about that the language is itself reursive or not $\endgroup$ – Noob Dec 25 '18 at 12:17
  • 1
    $\begingroup$ @rajendra Being "decidable" (or "recursive"; they are synonyms) is a characteristic of the language itself; hence, the latter version is what is meant. This also applies to the problem of deciding whether a language is recursively enumerable or not, which is also a language. $\endgroup$ – dkaeae Dec 25 '18 at 14:21
  • $\begingroup$ now you try to got my point , now tell me given a language how you are going to tell whether the language is recursive ( as said by you that recursive language is decidable and offcourse we are not talking about the membership problem) or not . as you said this is decidable so i just want to know how you get to that point . $\endgroup$ – Noob Dec 25 '18 at 16:12
  • 1
    $\begingroup$ @rajendra "Telling" whether a language is recursive or not is not the same as "deciding" it. The first entails a mathematical proof; the latter implies there is a TM (i.e., an automated procedure) at work. And I never said such a problem would be decidable; what I did say was every recursive language (as a language) is decidable. $\endgroup$ – dkaeae Dec 25 '18 at 16:27
1
$\begingroup$

You're talking about the following two problems:

  1. I give you a string and ask "Is it in this recursive language?"

  2. I give you a language and ask "Is this language recursive?"

You're assuming that they're the same problem, but they're not.

$\endgroup$
  • $\begingroup$ yeah but i have reached my verdict that , the answer to problem1 is decidable and problem 2 is undecidable. am i right? $\endgroup$ – Noob Jan 1 at 3:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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