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.