Alexander Kreuzer: On the Uniform Computational Content of Computatibility Theory

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 2 September 2015, 17:00 hrs

Room: S17#04-06, Department of Mathematics, NUS

Speaker: Alexander Kreuzer

Title: On the Uniform Computational Content of Computatibility Theory


We demonstrate that the Weihrauch lattice can be used to study the
uniform computational content of computability theoretic properties
and theorems in one common setting.
The properties that we study include diagonal non-computability,
hyperimmunity, complete extensions of Peano arithmetic, 1-genericity,
Martin-Loef randomness and cohesiveness. The theorems that we include
in our case study are the Low Basis Theorem of Jockusch and Soare, the
Kleene-Post Theorem and Friedman’s Jump Inversion Theorem. It turns
out that all the aforementioned properties and many theorems in
computability theory, including all theorems that claim the existence
of some Turing degree, have very little uniform computational content.
They are all located outside of the upper cone of binary choice (also
known as LLPO) and we call problems with this property
indiscriminative. Since practically all theorems from classical
analysis whose computational content has been classified are
discriminative, our observation could yield an explanation for why
theorems and results in computability theory typically have very
little direct consequences in other disciplines such as analysis.

Two notable exceptions to this are the Low Basis Theorem which is
discriminative, this is perhaps why it is considered to be one of the
most applicable theorems in computability theory, and the Baire
category theorem (or to be precise certain formulations of it) which
is an indiscriminative principle occurring in mathematical
analysis. We will see that the Baire category theorem is related to

In some cases a bridge between the indiscriminative world and the
discriminative world of classical mathematics can be established via a
suitable residual operation and we demonstrate this in case of the
cohesiveness problem, which turns out to be the quotient of two
discriminative problems, namely the limit operation and the jump of
Weak Koenig’s Lemma.

This is joint work with Vasco Brattka and Matthew Hendtlass.

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.