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

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Abstract:

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

1-genericity.

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.