Penn Arts & Sciences Logo

Logic and Computation Seminar

Monday, March 24, 2014 - 3:00pm

Thomas Kent

Marywood University

Location

University of Pennsylvania

2C4

As is commonly known, Turing reducibility allows us to query an oracle set for both positive and negative information and gives rise to the familiar Turing degrees. On the other hand, enumeration reducibility can be viewed as allowing only the transmission of positive information. Amazingly enough, restricting the manner in which we can gather information from oracles actually gives rise to a very rich structure known as the enumeration-degrees. In fact, there is a very natural embedding of the Turing degrees into the enumeration degrees and so the enumeration degrees can be viewed as an extension of the Turing degrees. This structure is so rich that the eminent computability theorist, Andrea Sorbi, once described it as being a ``zoo. ´´ So pack your bags and come along for an exciting sightseeing tour as we seek out some of the more exotic creatures that exist in this land. If there is time, we will make a short foray in the country of the $s$- degrees to take a peek at what lies behind those distant borders.