All Articles

Computability theory beyond the countable

Computability is very well-understood in the context of the natural numbers: essentially every
reasonable model of computation gives rise to the same notion. This in turn provides a
framework for studying the role of (non)computability throughout “countable mathematics.” In
particular, we can study the complexity of specific structures of interest (“computable structure
theory”) or the types of constructions needed for proofs of various theorems (“reverse
mathematics”).
However, things become much more difficult when we look beyond the countable; for example,
it is not at all clear how to talk about the computability-theoretic complexity of the field of real
numbers or of various forms of the axiom of choice. In this talk I’ll present work on extending
the computability-theoretic analysis of mathematics to situations far from the natural numbers:
uncountable computable structure theory and higher-order reverse mathematics.