1
$\begingroup$

When we say a class of languages is decidable we mean that the membership problem can be solved. However even though the membership problem is solvable for the class, there may exists some problems for the same class which are undecidable. For example Context free languages are decidable yet the problem of determining whether the language generated by context free grammar is unambiguous is undecidable.

I want to know some undecidable problems for recursive languages. Please don't problems related to context free and context sensitive language and then say that these languages are also recursive. The problems I want must be for only recursive languages and not for any proper subset of this class.

Improve this question
$\endgroup$
3
  • $\begingroup$ "The problems I want must be for only recursive languages" -- Why? That sounds like a silly restriction: every problem that is undecidable for R is undecidable for unfinitely many subclasses! $\endgroup$
    – Raphael ♦
    Oct 25, 2017 at 9:42
  • $\begingroup$ How do you want to represent recursive languages as inputs? TMs that decide them? $\endgroup$
    – Raphael ♦
    Oct 25, 2017 at 9:45
  • $\begingroup$ There is something wrong with your problem statement. A language is already in some sense a problem, namely membership problem. So if that language is decidable then it cannot be undecidable. $\endgroup$
    – fade2black
    Oct 25, 2017 at 10:42

1 Answer 1

Reset to default
2
$\begingroup$

For recursive languages, membership is decidable by definition, so most undecidable questions with regards to them will involve quantifiers. It's decidable to check if there's a given input is accepted, but it's undecidable to check whether a recursive language accepts any string, for example.

That said, questions like this are almost never phrased in terms of recursive languages, because there's representation of languages that captures exactly the recursive languages. Generally we represent languages as Turing Machines, but these characterize the recursively enumerable languages.

When it comes to RE, there's something called Rice's theorem,which says that any non trivial property of RE languages is undecidable. This holds for anything that's a property of the language itself, not just the specific representation.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I'm not quite clear what your point is here. Is it: "you can't ask for problems on recursive languages; you need to fix a representation resp. an encoding"? $\endgroup$
    – Raphael ♦
    Oct 25, 2017 at 9:46

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.