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.

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).