Series: Penn State Logic Seminar

 Date: Tuesday, October 18, 2005

 Time: 2:30 - 3:45 PM

 Place: 106 McAllister Building

 Speaker: Stephen G. Simpson, Penn State, Mathematics

 Title: An Introduction to Degrees of Unsolvability, part 1

 Abstract: 

   Beginning with fundamental work of Turing in the 1930's, degrees of
   unsolvability have become an important and highly developed
   research direction within mathematical logic.  The purpose of this
   series of talks is to provide an introduction to the subject.
   Among the concepts to be explored are: computable functions, the
   Halting Problem, many-one reducibility, recursive enumerability,
   Turing oracles, Turing reducibility, Turing degrees, Turing
   completeness, the arithmetical hierarchy, relativization, the
   Turing jump operator, basis theorems, mass problems, weak
   reducibility and weak degrees (a.k.a., Muchnik reducibility and
   Muchnik degrees).  In addition, we shall mention connections with
   other topics in mathematical logic, such as undecidability and
   representability.