What is the difference between recursive and recursively enumerated languages

Question

I was wondering what is the difference between recursive and recursively enumerated languages ​​in terms of stopping and Turing machines. I know that recursively enumerated languages ​​are a subset of recursive languages, but I'm not sure about the differences outside of this.

Answer 1

You have a connection between R and RE back: R is a (correct) subset of RE. Basically, a recursive language is one for which you have a complete decisive process.

Recall the definition of recursively enumerated languages ​​as one for which a partial decider exists ; that is, a Turing machine, which, given as an input word above your alphabet, will either correctly accept / reject the word in accordance with your language, or if the word is not in your language, it can loop forever.

A recursive language, in contrast, is one for which a full receiver exists, i.e. one that will never quote, and always stops in a state of acceptance or rejection.

Putting these two definitions next to each other, it is obvious that the recursive language is also recursively enumerable, since the complete decisive element is also partial (it simply never “selects” the loop, but does not stop with the correct answer).

Answer 2

The main difference is that in a recursively enumerated language, the machine stops for input strings that are in L., but for input strings that are not in L, it can stop or not stop.

When we approach a recursive language, it always stops, regardless of whether it is accepted by the machine or not. if it is accepted, it reaches (q accept) and stops. and if the machine is not accepted, it directly reaches (q stop).