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.
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).
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments