Series: Penn State Logic Seminar Date: Tuesday, February 26, 2002 Time: 2:30 - 3:45 PM Place: 113 McAllister Building Speaker: Stephen G. Simpson, Penn State, Mathematics Title: Recursively Enumerable Turing Degrees Abstract: In this talk we discuss some research inspired by Turing's epochal result on unsolvability of the Halting Problem. Two problems are said to be of the same Turing degree (a.k.a., degree of unsolvability) if each of the problems is solvable using an oracle for the other. A problem is of Turing degree 0 if and only if it is solvable outright, using no oracle. Thus 0 is the minimum Turing degree. Kleene and Post constructed a pair of problems whose Turing degrees are incomparable and strictly less than the Turing degree of the Halting Problem. It is well known that the Halting Problem is recursively enumerable. A Turing degree is said to be r.e. if it is the Turing degree of a recursively enumerable problem. The Turing degree of the Halting Problem can be characterized as the maximum r.e. Turing degree. Friedberg and Muchnik refined the result of Kleene and Post, by constructing a pair of incomparable r.e. Turing degrees. Subsequently, many other results concerning r.e. Turing degrees have been discovered. A reference for this material is the book by Robert Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, 1987.