On the Uniform Computational Content of Computability Theory

Vasco Brattka, Matthew Hendtlass, Alexander P. Kreuzer

Published 2015-01-02Version 1

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-L\"of 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. A notable exception in our case study is 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. 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 K\H{o}nig's Lemma.