What is the difference between recursive and recursively enumerable languages

Question

I was wondering what the difference between recursive and recursively enumerable languages is in terms of halting and Turing Machines. I know that recursively enumerable languages are a subset of recursive languages but I'm not sure about the difference beyond that.

Eleonoreleonora

Might be better suited for cstheory.stackexchange.com or cs.stackexchange.com – Odoriferous

I'm voting to close this question as off-topic because it is about the theory of computation, not programming. – Morelos

@RaymondChen I think the fact that there are "theory" and "computation-theory" tags justifies my question. – Eleonoreleonora

Answer 1

You have the relationship between R and RE backwards: R is a (proper) subset of RE. Basically, a recursive language is one for which you have a total decider.

Recall a definition of recursively enumerable languages as one for which a partial decider exists; that is, a Turing machine which, given as input a word over your alphabet, will either correctly accept/reject the word according to your language, or if the word is not in your language, it may loop forever.

A recursive language, in contrast, is one for which a total decider exists, i.e. one that will never loop, and always halt in either an accepting or a rejecting state.

Putting these two definitions next to each other, it is obvious that a recursive language is also recursively enumerable, since the total decider is also a partial one (it just never "chooses" to loop instead of halting with a correct answer).

Offprint

Answer 2

The main difference is that in recursively enumerable language the machine halts for input strings which are in language L. but for input strings which are not in L, it may halt or may not halt.

When we come to recursive language it always halt whether it is accepted by the machine or not. if it accepted it reaches at (q accept) and halt. and if not accepted by the machine it directly reach (q halt).

Kinghorn

Answer 3

The halting problem is the canonical example of a RE but non R problem

When trying to split complexity classes, it always good to have an example in mind that belong to one but not the the other.

In this case, the canonical example is the language corresponding to the halting problem decision problem:

HALT = All Turing Machine/input pairs that halt

It is well known that the halting problem cannot be deterministically resolved by any Turing machine, and therefore the language HALT is not in R.

But HALT is obviously in RE.

We recall the definition of a recursively enumerable languages as:

A RE language is a language such that there exists a Turing machine that halts on every member of the language with a yes output, and possibly runs forever on non-members

So we just take a Turing machine that simulates another Turing machine (universal Turing machine). Then that machine will halt on every member of HALT, and so HALT is in RE.

This fact alone should highlight how much harder RE is than R: RE contains undecidable problems, for which is it prevenly impossible to design an algorithm for! R, as a direct consequence of its definition, doesn't.

Non-RE problems

It is also helpful to have a look at examples that bound both:

• https://cs.stackexchange.com/questions/52503/non-recursively-enumerable-languages
• https://cs.stackexchange.com/questions/12747/relationship-between-undecidable-problems-and-recursively-enumerable-languages

The canonical examples is the complement of HALT: the language of all non-halting TM/input pairs.

Burson