University Seminar- Computability, Complexity, and Algebraic Structure-Basis theorems in computability

Time: Friday, May 2, 2:20 – 3:20pm

Place: Phillips 209

Speaker:  Henry Klatt, GWU

Title: Basis theorems in computability

Abstract:  Basis theorems in computability theory show that certain natural classes of sets or functions must contain elements that aren't too complicated.  The low basis theorem says that any Pi^0_1 class of sets of naturals must contain a set whose Turing jump is as small as possible.  The Gandy basis theorem states that any Sigma^1_1 set of functions must contain an element that cannot compute any non-computable ordinals.  These two theorems seem distinct at first glance, but through successive refinement, they rhyme more and more, ultimately providing deep insight into the ideas of so-called higher recursion theory: the gem of mathematical logic that bridges the gap between computability and set theory. In this talk, we will prove both basis theorems in an attempt to highlight their similarity, and to gain insight into the treasure of higher recursion theory.