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.
Mathematical Logic at Penn State
Department of Mathematics