Series: Penn State Logic Seminar

Date: Tuesday, November 13, 2001

Time: 2:30 - 3:45 PM

Place: 306 Boucke Building

Speaker: William Calhoun, Bloomsburg University, Mathematics

Title: The Computably Enumerable Turing Degrees: An Algebraic Approach


A set of natural numbers is computably enumerable (c.e.) if it can be
generated by a Turing machine that is allow to run forever.  We say A
is Turing reducible to B if B can be computed by a Turing Machine with
an oracle for A.  The c.e. sets are partially ordered by Turing
reducibility, and the equivalence classes are called c.e. Turing
degrees.  It has been almost 50 years since the independent proofs by
Friedberg [1957] and Muchnik [1956] that there are incomparable
c.e. sets.  In that time, the structure of the c.e. degrees has been
studied intensively.  A few nice global properties have been
discovered, but many results indicate the complexity of the structure.
Over the last decade a new direction for research has been to study
the ideals and homomorphic images of the structure.  Perhaps this
algebraic approach will provide a clearer picture of the global
structure.  This talk will be a nontechnical survey of "algebraic"
computability theory, including recent work by Englert, Lerman and
Wald and by Lerman and myself.