I am studying for a computational theory exam and having problem with a concept.
What exactly is the difference between a recursively enumerable language and a recursive language?
I know recursive is a subset of recursively enumerable, but what sets them apart?
Also, I need to know how this relates to Turing machines. It seems a lot of websites just blabber on and on about sets and such… I don’t care about that, I just want to know how they are different (in plain English) and how they affect Turing machines.
A language is recursive if there exists a Turing machine that accepts every string of the language and rejects every string (over the same alphabet) that is not in the language.
<snip>
*A language is recursively enumerable if there exists a Turing machine that accepts every string of the language, and does not accept strings that are not in the language. (Strings that are not in the language may be rejected or may cause the Turing machine to go into an infinite loop.) *
IOW, a recursive language can’t go into an infinite loop, it has to clearly reject the string, but a recursively enumerable language can go into an infinite loop.
Remember that there are three possible outcomes of executing a Turing machine over a given input. The Turing machine may
[ol]
[li]Halt and accept the input;[/li][li]Halt and reject the input; or[/li][li]Never halt.[/li][/ol]
A language is recursive if there exists a Turing machine that accepts every string of the language and rejects every string (over the same alphabet) that is not in the language.
Note that, if a language L is recursive, then its complement -L must also be recursive. (Why?)
A language is recursively enumerable if there exists a Turing machine that accepts every string of the language, and does not accept strings that are not in the language. (Strings that are not in the language may be rejected or may cause the Turing machine to go into an infinite loop.)
Clearly, every recursive language is also recursively enumerable. It is not obvious whether every recursively enumerable language is also recursive.
Note on terminology: Turing machines aren’t “recursive.” The terminology is borrowed from recursive function theory (Turing machines are equivalent to general recursive functions). The terms really don’t make sense in this context, so don’t worry about trying to make them make sense.
To enumerate a set is to place the elements of the set in a one-to-one correspondence with the natural numbers.
The set of all strings over an alphabet is denumerable (think of a string as a number in an ||-ary number system). The strings in a language form a subset of the set of all strings over . But can we enumerate the strings in a language?
Very well done indeed. Here is a definition for sets of integers.
A set of integers is recursive if there is a machine that can test any integer and calculate whether it is in the set. An example is the set of primes. Take any integer and try to divide by all smaller numbers (>1) until you find a divisor–or not. On the other hand, a recursively enumerable set is one for which you have a way to generate all its elements but for which you might not be able to test whether a given number is a member of the set. For example, the sequence of primes generated by taking the first n of them, say p_1,…,p_n and then letting P_{n+1} be the least prime divisor of p_1p_2…*p_n + 1. Does 5 appear ever? I don’t know. The sequence might be recursive, but I don’t know.
In terms of a language a generative grammar can, in principle, generate all the grammatical sentences of the language, pretty much what is meant by generative. But whether we have a grammatical tester that can tell if a sentence is grammatical is problematic. Most people will find the famous sentence “The horse raced past the barn fell” ungrammatical at first glance, which suggests that we use heuristics to judge, but don’t have a real engine.
