An Introduction to Degrees of Unsolvability, part 2

Series: Penn State Logic Seminar

 Date: Tuesday, October 25, 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 2

 Abstract: 

   In the previous talk we discussed computable functions, the Halting
   Problem, many-one reducibility, recursive enumerability, and the
   arithmetical hierarchy.  In this talk we shall discuss Turing
   oracles, Turing reducibility, and the Turing jump operator.  These
   fundamental concepts provide a method of comparing and classifying
   unsolvable problems, according to their degrees of unsolvability.
   We shall discuss a theorem due to Post which exposes a close
   relationship between degrees of unsovability and the arithmetical
   hierarchy.