Department of Mathematics

Van Vleck Hall, 480 Lincoln Drive, Madison, WI

Math 873: Advanced Topics in Foundations (Fall)


Noah Schweber (Fall 2017): Generalized computability theory

A couple years after Friedberg–Muchnik, Kleene started looking at extending computability beyond the reals. This theme was quickly adopted by others. Initially the focus was on extending computability to higher-type functionals (e.g. maps from reals to naturals), but further directions emerged in short order—computability in arbitrary structures and more set-theoretic versions of computability in particular.

We'll look at various ways to generalize computability—amongst them, alpha- and E-recursion and various notions of computability in higher types. We'll also look a bit at the versions of reverse mathematics and computable structure theory associated to these computability theories; this is a fairly untouched area, with lots of accessible and interesting open questions. Along the way, we'll wind up doing some set theory—forcing, descriptive set theory, and some basic inner model theory.

(The goal of the class being to introduce a number of variations on the computability "theme," we will be blackboxing or avoiding entirely some of the more technical results; we will focus instead on clearly introducing the ideas and basic results in each approach.)


UW-Madison Department of Mathematics
Van Vleck Hall
480 Lincoln Drive
Madison, Wi  53706

(608) 263-3054

Contact Us

Got a question about
accessibility, content
or structure of this website?