Timeline for Is there a language in $RE \setminus R$ which is not $RE$-complete?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 9, 2011 at 15:45 | comment | added | Andrés E. Caicedo | @puzne: It is not just Turing degrees that you were looking for, since you are specifically asking for r.e. sets. What you are interested in is the class of r.e. degrees, and Soare's book mentioned before by Carl is probably the best reference to get started. If you want to get a quick idea of the landscape, you may want to read first the nice paper by Shore, "Degree Structures: Local and Global Investigations", Bulletin of Symbolic Logic, 12 (2006), 369-389. It is available at his website, math.cornell.edu/~shore/papers/pdf/RetPresrv2.pdf | |
| Apr 9, 2011 at 12:36 | comment | added | puzne | Thanks all. I guess the term I was missing was "Turing degree". With that I would have found the following wikipedia entry, which I am listing for future reference. en.wikipedia.org/wiki/Turing_degree | |
| Apr 9, 2011 at 12:27 | vote | accept | puzne | ||
| Apr 9, 2011 at 2:22 | comment | added | Carl Mummert | You're right - there is no known example of a "natural" intermediate r.e. degree. | |
| Apr 9, 2011 at 2:17 | history | answered | John Stillwell | CC BY-SA 3.0 |