Weihrauch Degrees, Omniscience Principles and Weak Computability

Abstract

In this paper we study Weihrauch reducibility for multi-valued functions on represented spaces. We call the corresponding equivalence classes Weihrauch degrees and we show that the corresponding partial order induces a lower semi-lattice with the disjoint union of multi-valued functions as greatest lower bound operation. We prove that parallelization is a closure operator for this semi-lattice and the parallelized Weihrauch degrees even form a lattice with the product of multi-valued functions as greatest lower bound operation. We show that the Medvedev lattice and hence Turing degrees can be embedded into the parallelized Weihrauch lattice in a natural way. We study the limited principle of omniscience LPO, the lesser limited principle of omniscience LLPO and their parallelizations. We prove that parallelized LLPO is equivalent to Weak K"onig's Lemma and hence to the Hahn-Banach Theorem in this new and very strong sense. We call a multi-valued function weakly computable if it is reducible to the Weihrauch degree of parallelized LLPO and we present a new proof that the class of weakly computable operations is closed under composition. This proof is based on a computational version of Kleene's ternary logic. Moreover, we characterize weakly computable operations on computable metric spaces as operations that admit upper semi-computable compact-valued selectors and we prove that any single-valued weakly computable operation is already computable in the ordinary sense.

References in corpus (1)

• Effective Choice and Boundedness Principles in Computable Analysis

Cited by in corpus (28)

• Closed Choice and a Uniform Low Basis Theorem
• The Bolzano-Weierstrass Theorem is the Jump of Weak König's Lemma
• Effective Choice and Boundedness Principles in Computable Analysis
• Computability and analysis: the legacy of Alan Turing
• Complexity Theory for Operators in Analysis
• Probabilistic Computability and Choice
• Non-deterministic computation and the Jayne-Rogers Theorem
• Turing machines on represented sets, a model of computation for Analysis
• Connected Choice and the Brouwer Fixed Point Theorem
• Completion of Choice
• On computability and disintegration
• Wadge-like reducibilities on arbitrary quasi-Polish spaces
• On the Uniform Computational Content of Computability Theory
• On the existence of a connected component of a graph
• Algebraic properties of the first-order part of a problem
• Many-one reductions and the category of multivalued functions
• On the Uniform Computational Content of the Baire Category Theorem
• Instance reducibility and Weihrauch degrees
• Computability and Analysis, a Historical Approach
• The Vitali Covering Theorem in the Weihrauch Lattice
• Projection operators in the Weihrauch lattice
• Primitive recursive reverse mathematics
• Stashing And Parallelization Pentagons
• Banach's theorem in higher order reverse mathematics
• Comodule Representations of Second-Order Functionals
• Computability of Initial Value Problems
• The Weihrauch lattice at the level of ${\mathbf{\Pi }}_1^1{-\mathsf{CA}}_0$: the Cantor-Bendixson theorem
• A jump operator on the Weihrauch degrees