Hierarchy Theory: Where Definition and Computation Meet

The priority method

A set (of natural numbers) is computable if there is an algorithm that, on input n, decides whether or not n is in the set. A set is computably enumerable (c.e.) if there is an algorithm that can list the elements of the set, though not necessarily in numerical order. Turing's Halting Problem is one of many naturally occuring sets that are c.e. but not computable.

An interesting phenomenon that was noticed early on in the development of computability theory is that all such sets that were known shared the property of being as computability-theoretically complicated as a c.e. set can be, in a precise sense captured by a notion of relative computability known as Turing reducibility. Post's Problem asked whether there are any c.e. sets that are neither computable nor as powerful as the Halting Problem. The priority method was introduced by Friedberg and Muchnik independently in the 1950s to give a positive answer to this problem, and has since been used to construct sets with a variety of interesting computability-theoretic properties.

After an introduction to the basics of computability theory, these lectures will explain the priority method and discuss some applications.