Provable (and Unprovable) Computability Part 2

Stan Wainer, University of Leeds. Part of the Proofs, Constructions, and Computations seminar series.

The second of these two talks will survey the rather old and well-worn topic of subrecursive hierarchies and how they arise in classifying the computational strengths of theories (from polytime arithmetic up to Pi^1_1-CA_0 and beyond).  However the underlying context here ("predicative" or "tiered" induction) and associated method (Buchholz' Big Omega rule) will provide a somewhat newer, up-to-date flavour.  Independence results also naturally to crop up alongside these hierarchies.  Two well-known ones will begin and end the talks.