Computability Learning Seminar

Thursday, March 9, 2023 2:30 pm - 2:30 pm EST

Luke MacLean, Department of Pure Mathematics, University of Waterloo


In computability theory one is often tasked with building a computable object using non-computable information. A common approach to overcoming this issue involves a priority construction. We use computable approximations to the information that we want to use in our construction and devise a list of requirements that we would like to have met by the end of the construction. As our approximations may change during the construction, we may have to change things that we have already built to preserve our requirements, and in doing so we might injure other requirements. To ensure that all requirements are met, we assign a priority-ordering on them so that certain things are preserved and cannot be injured by lower priority requirements. 

However, the more complicated the information, the more injury there will be occurring between requirements. To simplify the process many different metatheorems have been proposed by many famous computability theorists. A metatheorem is a set of conditions that, if met, guarantee the success of a priority construction. In this talk I will motivate the need for metatheorems and talk about a few different examples of metatheorems and their applications.

MC 5403