1
$\begingroup$

What is the point and application of recursive and recursive enumerable languages. Finite Automaton is used for pattern matching, designing computer architecture and protocols, CFG is used for designing compilers but what about Recursive and Recursive enumerable languages?

$\endgroup$
1
$\begingroup$

Recursive languages correspond to whatever can be computed in your favorite programming languages. Recursively enumerable languages correspond to whatever can be enumerated in your favorite programming languages — for example, all provably true mathematical theorems.

Your question assumes a particular list of canonical language classes, including four classes: regular languages, context-free languages, recursive languages, and r.e. languages. However, this list is rather arbitrary, and it omits modern complexity classes, including the all-important classes $\mathsf{P}$ and $\mathsf{NP}$.

The class $\mathsf{P}$ is intended to capture what can be computed efficiently (whether it succeeds in this goal is another question). The class $\mathsf{NP}$ captures problems which can be solved using "exhaustive search", that is, SAT solvers, IP solvers, and the like.

It turns out that $\mathsf{NP}$ captures many natural combinatorial problems, many of which are "equally hard". This leads most researchers to think that these "equally hard" problems are actually hard, that is, cannot be computed efficiently, a conjecture known as $\mathsf{P} \neq \mathsf{NP}$.

Computational complexity theory mentions many other complexity classes of interest. Practically speaking, a relevant class of languages are those which can be decided in quasilinear time (broadly construed) in the RAM machine model. This class roughly corresponds to problems which can be solved in practice even on "big data".

$\endgroup$
  • $\begingroup$ Thanks for the answer. What does 'recursive' mean when we talk about REC and RE language. Also, could you please further explain about enumeration part? $\endgroup$ – Vikas Yadav Jul 24 '18 at 15:13
  • $\begingroup$ The name recursive stems from a historically important paper of Gödel. From more on this topic, I recommend Soare's historical survey. Regarding enumerability, hopefully this will come up during your studies. $\endgroup$ – Yuval Filmus Jul 24 '18 at 15:27

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.