# Recursively enumerable vs. Recursive languages **URL:** \ **Category:** Factual Questions\ **Created:** [December 8, 2004, 1:13am UTC](https://boards.straightdope.com/t/recursively-enumerable-vs-recursive-languages/278658 "2004-12-08T01:13:12Z")\ **Posts on this page:** 11\ **Page:** 1
**Author:** ![Hermitian](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/hermitian/32/470_2.png) [@Hermitian](https://boards.straightdope.com/u/Hermitian)\ **Post date:** [December 8, 2004, 1:13am UTC](https://boards.straightdope.com/t/recursively-enumerable-vs-recursive-languages/278658/1 "2004-12-08T01:13:12Z")
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. Thanks a ton. ---
**Author:** ![dre2xl](https://avatars.discourse-cdn.com/v4/letter/d/34f0e0/32.png) [@dre2xl](https://boards.straightdope.com/u/dre2xl)\ **Post date:** [December 8, 2004, 1:30am UTC](https://boards.straightdope.com/t/recursively-enumerable-vs-recursive-languages/278658/2 "2004-12-08T01:30:03Z")
[http://www.netaxs.com/people/nerp/automata/relang6.html](http://www.netaxs.com/people/nerp/automata/relang6.html) _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._ \ \*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. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [December 8, 2004, 2:50am UTC](https://boards.straightdope.com/t/recursively-enumerable-vs-recursive-languages/278658/3 "2004-12-08T02:50:46Z")
> [@Hermitian](#): > > 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. You’re studying computational theory and you want plain English explanations? You’re in for a rough time. ---
**Author:** ![dre2xl](https://avatars.discourse-cdn.com/v4/letter/d/34f0e0/32.png) [@dre2xl](https://boards.straightdope.com/u/dre2xl)\ **Post date:** [December 8, 2004, 12:37pm UTC](https://boards.straightdope.com/t/recursively-enumerable-vs-recursive-languages/278658/4 "2004-12-08T12:37:30Z")
> [@ultrafilter](#): > > You’re studying computational theory and you want plain English explanations? > > You’re in for a rough time. I really had to bite my tongue to stop from saying something along these lines, too. 😉 ---
**Author:** ![Capt.Ridley\_s\_Shooting\_Party](https://avatars.discourse-cdn.com/v4/letter/c/cc9497/32.png) [@Capt.Ridley\_s\_Shooting\_Party](https://boards.straightdope.com/u/Capt.Ridley_s_Shooting_Party)\ **Post date:** [December 8, 2004, 12:39pm UTC](https://boards.straightdope.com/t/recursively-enumerable-vs-recursive-languages/278658/5 "2004-12-08T12:39:52Z")
What a coincidence. I have an exam on this subject this afternoon. ---
**Author:** ![sharma24h](https://avatars.discourse-cdn.com/v4/letter/s/51bf81/32.png) [@sharma24h](https://boards.straightdope.com/u/sharma24h)\ **Post date:** [April 29, 2013, 7:05am UTC](https://boards.straightdope.com/t/recursively-enumerable-vs-recursive-languages/278658/6 "2013-04-29T07:05:01Z")
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? :smack: [Sumit](http://orbittechmind.com) ---
**Author:** ![Terminus\_Est](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/terminus_est/32/3087_2.png) [@Terminus\_Est](https://boards.straightdope.com/u/Terminus_Est)\ **Post date:** [April 29, 2013, 7:21am UTC](https://boards.straightdope.com/t/recursively-enumerable-vs-recursive-languages/278658/7 "2013-04-29T07:21:46Z")
One would hope that the OP has already taken his exam **nine years ago**. ---
**Author:** ![leahcim](https://avatars.discourse-cdn.com/v4/letter/l/b4bc9f/32.png) [@leahcim](https://boards.straightdope.com/u/leahcim)\ **Post date:** [April 29, 2013, 11:24am UTC](https://boards.straightdope.com/t/recursively-enumerable-vs-recursive-languages/278658/8 "2013-04-29T11:24:37Z")
> [@Terminus\_Est](#): > > One would hope that the OP has already taken his exam **nine years ago**. Maybe he’s still waiting for his Turing machine to reject some string that isn’t in the recursively enumerable language. ---
**Author:** ![Darth\_Panda](https://avatars.discourse-cdn.com/v4/letter/d/ee7513/32.png) [@Darth\_Panda](https://boards.straightdope.com/u/Darth_Panda)\ **Post date:** [April 29, 2013, 11:44am UTC](https://boards.straightdope.com/t/recursively-enumerable-vs-recursive-languages/278658/9 "2013-04-29T11:44:39Z")
Poster rescued from 9 year loop. See [here](http://boards.straightdope.com/sdmb/showthread.php?t=290618) for details. ---
**Author:** ![WordMan](https://avatars.discourse-cdn.com/v4/letter/w/e8c25b/32.png) [@WordMan](https://boards.straightdope.com/u/WordMan)\ **Post date:** [April 29, 2013, 12:13pm UTC](https://boards.straightdope.com/t/recursively-enumerable-vs-recursive-languages/278658/10 "2013-04-29T12:13:02Z")
> [@Darth\_Panda](#): > > Poster rescued from 9 year loop. See [here](http://boards.straightdope.com/sdmb/showthread.php?t=290618) for details. Well done. ---
**Author:** ![Hari\_Seldon](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/hari_seldon/32/5173_2.png) [@Hari\_Seldon](https://boards.straightdope.com/u/Hari_Seldon)\ **Post date:** [April 29, 2013, 8:21pm UTC](https://boards.straightdope.com/t/recursively-enumerable-vs-recursive-languages/278658/11 "2013-04-29T20:21:01Z")
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\_1_p\_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.