Computable analysis
Minicourse On Computable Analysis
by Arno Pauly (Swansea)
Tue 22.5.2018 11-12, C122
Wed 23.5.2018 11-12, C124
Thu 24.5.2018 11-12, C124
Course contents
Lecture 1: How does computability work for infinite bit sequences? How can we lift that notion to interesting spaces such as real numbers? We will look into the resulting structure, and see that topological notions naturally appear. Properties like compactness or Hausdorffness characterize the computability of certain operations.
Lecture 2: We look into computability on specific structures and of specific operations. Examples will include the continuous functions on the unit interval, the space of probability measures over a given space and the collection of countable ordinals.
Lecture 3: Mathematical existence theorems give rise to computational tasks, where we would want to compute the object we are proving the existence of based on the parameters. A typical example is Brouwer's Fixed Point theorem, where we would want to compute a fixed point from the continuous function. Here, and in many other cases, this task turns out to be non-computable. Studying the degrees of non-computability (the Weihrauch degrees) lets us find out how non-constructive the theorems are, and to what extent partial or weaker solutions are possible. We will cover both the fundamental theory of Weihrauch degrees, and some concrete examples.