2
$\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?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ "Recursive" and "decidable" mean exactly the same thing. $\endgroup$
    – David Richerby
    Dec 31, 2018 at 22:03

2 Answers 2

Reset to default
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$.

Improve this answer
$\endgroup$
10
  • $\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$
    – rballiwal
    Dec 25, 2018 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$
    – rballiwal
    Dec 25, 2018 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, 2018 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$
    – rballiwal
    Dec 25, 2018 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, 2018 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.

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

Your Answer

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

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