Weihrauch Degrees, Omniscience Principles and Weak Computability

Details Weihrauch Degrees, Omniscience Principles and Weak Computability Weihrauch Degrees, Omniscience Principles and Weak Computability

2009-05-28

arxiv.org/abs/0905.4679v2

Journal of Symbolic Logic 76:1 (2011) 143-176

Mathematics

Logic

Scientific paper

10.2178/jsl/1294170993

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.

Affiliated with

Also associated with

No associations

Rating

Weihrauch Degrees, Omniscience Principles and Weak Computability does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Weihrauch Degrees, Omniscience Principles and Weak Computability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Weihrauch Degrees, Omniscience Principles and Weak Computability will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-294402