MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If any recursively enumerable language can be reduced by a mapping reduction to a language $L$, then $L$ is called $RE$ complete. In that case, $L$ must be in $RE\setminus R$. But are there languages in $RE\setminus R$ which are not $RE$ complete? Can anyone give an example of such a language? I'm sure this is well known, but it's not well known to me, and google doesn't help.

share|cite|improve this question
Yes, this is extremely well known, and covered in any reasonable recursion theory textbook at the graduate level. The usual construction makes a nonrecursive r.e. set that is not only intermediate in many-one degree, it's also intermediate in Turing degree. The construction, due independently to Friedberg and Muchnik, uses a priority argument. Soare's book or Rogers' book has all the details. – Carl Mummert Apr 9 '11 at 2:17
If by a mapping reduction from $A$ to $B$ you mean a recursive function $f$ such that $a \in A$ iff $f(a) \in B$, then it's somewhat easier than a priority argument. For these reductions, Post solved this problem using "simple sets" (r.e. sets whose complements contain no infinite r.e. sets). However, priority arguments are really beautiful and handle much more general sorts of reductions. – Henry Cohn Apr 9 '11 at 13:23
"Mapping reduction" is a (nonstandard) term that Sipser's computability textbook uses to refer to many-one reductions. It's a fine book but not focused at all on classical computability theory. – Carl Mummert Apr 9 '11 at 15:24
As Carl said, the construction by Friedberg and Muchnik uses a priority argument. It may be worth adding that they (indepedently) invented the priority method for just this problem (known as Post's problem). So in a sense, this question was at the root of much of the last half-century's development of recursion theory. – Andreas Blass Apr 9 '11 at 22:49
up vote 1 down vote accepted

Examples of such languages are not easy to describe, and I think no "naturally-occurring" example is known. However, Muchnik and Friedberg found examples in 1957, and Friedberg's example is here.

share|cite|improve this answer
You're right - there is no known example of a "natural" intermediate r.e. degree. – Carl Mummert Apr 9 '11 at 2:22
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. – puzne Apr 9 '11 at 12:36
@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, – Andrés Caicedo Apr 9 '11 at 15:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.