episciences.org_7225_1674948453
1674948453
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Logical Methods in Computer Science
18605974
12
20
2021
Volume 17, Issue 4
Stashing And Parallelization Pentagons
Vasco
Brattka
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
instancewise 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 instancewise 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 computabilitytheoretic
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 stashingparallelization 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 noncomputability problem. This
supports the slogan that "noncomputability is the parallelization of
discontinuity".
12
20
2021
7225
https://creativecommons.org/licenses/by/4.0
arXiv:2102.11832
10.48550/arXiv.2102.11832
https://arxiv.org/abs/2102.11832v2
https://arxiv.org/abs/2102.11832v1
10.46298/lmcs17(4:20)2021
https://lmcs.episciences.org/7225

https://lmcs.episciences.org/8872/pdf

https://lmcs.episciences.org/8872/pdf