Barbara Csima, University of Waterloo
Priority Arguments in Computability Theory
This term, Computability Learning Seminar will focus on Priority Arguments. Priority Arguments are a common proof technique used in Computability Theory. A theorem is broken down to being equivalent to a list of requirements. These requirements are given a priority order, and a strategy is devised to meet all the requirements, making use of the priority order. In the early days of the subject, a big question (Post’s Problem -1944) was whether there were any non-computable computably enumerable (c.e.) sets that were not Turing equivalent to the halting set. The solution, from Friedberg (1957) and Muchnik (1956), was to construct a pair of Turing incomparable c.e. sets, using a finite injury priority argument. In this first talk, we will begin our examination of priority arguments by going through the proof of this theorem, introducing definitions and reviewing notions from Computability Theory as needed along the way.
MC 5403