Weihrauch Degrees, Omniscience Principles and Weak Computability

Vasco Brattka & Guido Gherardi
In this paper we study a reducibility that has been introduced by Klaus Weihrauch or, more precisely, a natural extension of this 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 show that parallelization is a closure operator for this semi-lattice and the parallelized...