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.
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ 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. $\endgroup$– Carl MummertApr 9, 2011 at 2:17
-
$\begingroup$ 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. $\endgroup$– Henry CohnApr 9, 2011 at 13:23
-
1$\begingroup$ "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. $\endgroup$– Carl MummertApr 9, 2011 at 15:24
-
2$\begingroup$ 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. $\endgroup$– Andreas BlassApr 9, 2011 at 22:49
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
answered Apr 9, 2011 at 2:17
-
$\begingroup$ You're right - there is no known example of a "natural" intermediate r.e. degree. $\endgroup$ Apr 9, 2011 at 2:22
-
$\begingroup$ 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 $\endgroup$– puzneApr 9, 2011 at 12:36
-
1$\begingroup$ @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 $\endgroup$ Apr 9, 2011 at 15:45