Timeline for Is there a language in $RE \setminus R$ which is not $RE$-complete?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 9, 2013 at 2:57 | review | Close votes | |||
| Jul 9, 2013 at 5:49 | |||||
| S Jul 9, 2013 at 0:01 | history | suggested | jeq | CC BY-SA 3.0 |
Typo in title
|
| Jul 8, 2013 at 23:31 | review | Suggested edits | |||
| S Jul 9, 2013 at 0:01 | |||||
| Apr 9, 2011 at 22:49 | comment | added | Andreas Blass | 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. | |
| Apr 9, 2011 at 15:24 | comment | added | Carl Mummert | "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. | |
| Apr 9, 2011 at 13:23 | comment | added | Henry Cohn | 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. | |
| Apr 9, 2011 at 12:27 | vote | accept | puzne | ||
| Apr 9, 2011 at 2:19 | history | edited | Carl Mummert |
edited tags; edited tags
|
|
| Apr 9, 2011 at 2:17 | answer | added | John Stillwell | timeline score: 1 | |
| Apr 9, 2011 at 2:17 | comment | added | Carl Mummert | 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. | |
| Apr 9, 2011 at 1:49 | history | asked | puzne | CC BY-SA 3.0 |