Stashing And Parallelization Pentagons
arXiv:2102.11832 · doi:10.46298/lmcs-17(4:20)2021
Abstract
Parallelization is an algebraic operation that lifts problems to sequences in a natural way. Given a sequence as an instance of the parallelized problem, another sequence is a solution of this problem if every component is instance-wise a solution of the original problem. In the Weihrauch lattice parallelization is a closure operator. Here we introduce a dual operation that we call stashing and that also lifts problems to sequences, but such that only some component has to be an instance-wise solution. In this case the solution is stashed away in the sequence. This operation, if properly defined, induces an interior operator in the Weihrauch lattice. We also study the action of the monoid induced by stashing and parallelization on the Weihrauch lattice, and we prove that it leads to at most five distinct degrees, which (in the maximal case) are always organized in pentagons. We also introduce another closely related interior operator in the Weihrauch lattice that replaces solutions of problems by upper Turing cones that are strong enough to compute solutions. It turns out that on parallelizable degrees this interior operator corresponds to stashing. This implies that, somewhat surprisingly, all problems which are simultaneously parallelizable and stashable have computability-theoretic characterizations. Finally, we apply all these results in order to study the recently introduced discontinuity problem, which appears as the bottom of a number of natural stashing-parallelization pentagons. The discontinuity problem is not only the stashing of several variants of the lesser limited principle of omniscience, but it also parallelizes to the non-computability problem. This supports the slogan that "non-computability is the parallelization of discontinuity".
References in corpus (14)
- 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
- Weihrauch Degrees, Omniscience Principles and Weak Computability
- On the algebraic structure of Weihrauch degrees
- Probabilistic Computability and Choice
- Completion of Choice
- On the Uniform Computational Content of Computability Theory
- Weihrauch goes Brouwerian
- On the Uniform Computational Content of the Baire Category Theorem
- The Discontinuity Problem
- Game characterizations and lower cones in the Weihrauch degrees
- Inside the Muchnik Degrees I: Discontinuity, Learnability, and Constructivism
- Inside the Muchnik Degrees II: The Degree Structures induced by the Arithmetical Hierarchy of Countably Continuous Functions