For more information about this meeting, contact Stephen Simpson.
|Title:||Degrees of unsolvability and the Borel hierarchy|
|Speaker:||Stephen G. Simpson, Pennsylvania State University|
|Given a real number x, let x' be the halting problem relative to x. In other words, x' is the problem of deciding whether a given computer program which uses x as a Turing oracle will or will not eventually halt. By means of Gödel numbering, we may view x' as another real number. Thus we have an operator x |---> x' from real numbers to real numbers, known as the Turing jump operator. By iterating the Turing jump operator along the ordinal numbers which are computable using x as an oracle, we obtain what is known as the hyperarithmetical hierarchy relative to x. In this talk we explore the relationship between the hyperarithmetical hierarchy and the well-known hierarchy of Borel sets in Euclidean space indexed by the countable ordinal numbers. We sketch a proof of the following theorem of Kautz, 1991: If S is a Borel set at level alpha+2 in the effective Borel hierarchy relative to x, then S includes a set whose Lebesgue measure is the same as that of S and which is at level 2 of the effective Borel hierarchy relative to the alpha-th Turing jump of x. As time permits, we discuss recent refinements involving LR-reducibility.|
Room Reservation Information
|Date:||09 / 15 / 2009|
|Time:||02:30pm - 03:45pm|