1,721,027 research outputs found
A Galois connection between Turing jumps and limits
No full textLimit computable functions can be characterized by Turing jumps on the input
side or limits on the output side. As a monad of this pair of adjoint
operations we obtain a problem that characterizes the low functions and dually
to this another problem that characterizes the functions that are computable
relative to the halting problem. Correspondingly, these two classes are the
largest classes of functions that can be pre or post composed to limit
computable functions without leaving the class of limit computable functions.
We transfer these observations to the lattice of represented spaces where it
leads to a formal Galois connection. We also formulate a version of this result
for computable metric spaces. Limit computability and computability relative to
the halting problem are notions that coincide for points and sequences, but
even restricted to continuous functions the former class is strictly larger
than the latter. On computable metric spaces we can characterize the functions
that are computable relative to the halting problem as those functions that are
limit computable with a modulus of continuity that is computable relative to
the halting problem. As a consequence of this result we obtain, for instance,
that Lipschitz continuous functions that are limit computable are automatically
computable relative to the halting problem. We also discuss 1-generic points as
the canonical points of continuity of limit computable functions, and we prove
that restricted to these points limit computable functions are computable
relative to the halting problem. Finally, we demonstrate how these results can
be applied in computable analysis
Weihrauch goes Brouwerian
Full text linkWe prove that the Weihrauch lattice can be transformed into a
Brouwer algebra by the consecutive application of two closure operators in
the appropriate order: rst completion and then parallelization. The closure
operator of completion is a new closure operator that we introduce. It transforms
any problem into a total problem on the completion of the respective
types, where we allow any value outside of the original domain of the problem.
This closure operator is of interest by itself, as it generates a total version
of Weihrauch reducibility that is dened like the usual version of Weihrauch
reducibility, but in terms of total realizers. From a logical perspective completion
can be seen as a way to make problems independent of their premises.
Alongside with the completion operator and total Weihrauch reducibility we
need to study precomplete representations that are required to describe these
concepts. In order to show that the parallelized total Weihrauch lattice forms
a Brouwer algebra, we introduce a new multiplicative version of an implication.
While the parallelized total Weihrauch lattice forms a Brouwer algebra with
this implication, the total Weihrauch lattice fails to be a model of intuitionistic
linear logic in two dierent ways. In order to pinpoint the algebraic reasons
for this failure, we introduce the concept of a Weihrauch algebra that allows
us to formulate the failure in precise and neat terms. Finally, we show that
the Medvedev Brouwer algebra can be embedded into our Brouwer algebra,
which also implies that the theory of our Brouwer algebra is Jankov logic
Completion of choice
Full text linkWe systematically study the completion of choice problems in the Weihrauch lattice. Choice problems play a pivotal rôle in Weihrauch complexity. For one, they can be used as landmarks that characterize important equivalences classes in the Weihrauch lattice. On the other hand, choice problems also characterize several natural classes of computable problems, such as finite mind change computable problems, non-deterministically computable problems, Las Vegas computable problems and effectively Borel measurable functions. The closure operator of completion generates the concept of total Weihrauch reducibility, which is a variant of Weihrauch reducibility with total realizers. Logically speaking, the completion of a problem is a version of the problem that is independent of its premise. Hence, studying the completion of choice problems allows us to study simultaneously choice problems in the total Weihrauch lattice, as well as the question which choice problems can be made independent of their premises in the usual Weihrauch lattice. The outcome shows that many important choice problems that are related to compact spaces are complete, whereas choice problems for unbounded spaces or closed sets of positive measure are typically not complete
Stashing And Parallelization Pentagons
Full text linkParallelization 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"
Borel complexity of topological operations on computable metric spaces
No full textWe study the Borel complexity of topological operations on
closed subsets of computable metric spaces. The investigated operations
include set theoretic operations as union and intersection, but also typical
topological operations such as the closure of the complement, the
closure of the interior, the boundary and the derivative of a set. These
operations are studied with respect to different computability structures
on the hyperspace of closed subsets. These structures include positive
or negative information on the represented closed subsets. Topologically,
they correspond to the lower or upper Fell topology, respectively, and
the induced computability concepts generalize the classical notions of
r.e. or co-r.e. subsets, respectively. The operations are classified with respect
to effective measurability in the Borel hierarchy and it turns out
that most operations can be located in the first three levels of the hierarchy,
or they are not even Borel measurable at all. In some cases the
effective Borel measurability depends on further properties of the underlying
metric spaces, such as effective local compactness and effective
local connectedness
Weihrauch degrees, omniscience principles and weak computability
No full textIn this paper we study a reducibility that has been introduced by Klaus Weihrauch or, more
precisely, a natural extension 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. It turns out that parallelization is a closure operator for this semi-lattice and that the par-
allelized Weihrauch degrees even form a lattice into which the Medvedev lattice and the Turing degrees
can be embedded. The importance of Weihrauch degrees is based on the fact that multi-valued functions
on represented spaces can be considered as realizers of mathematical theorems in a very natural way and
studying the Weihrauch reductions between theorems in this sense means to ask which theorems can be
transformed continuously or computably into each other. As crucial corner points of this classification
scheme the limited principle of omniscience LPO, the lesser limited principle of omniscience LLPO and
their parallelizations are studied. It is proved that parallelized LLPO is equivalent to Weak König’s Lemma
and hence to the Hahn–Banach Theorem in this new and very strong sense. We call amulti-valued function
weakly computable if it is reducible to the Weihrauch degree of parallelized LLPO and we present a new
proof, based on a computational version of Kleene’s ternary logic, that the class of weakly computable
operations is closed under composition. Moreover, weakly computable operations on computable metric
spaces are characterized as operations that admit upper semi-computable compact-valued selectors and it
is proved that any single-valued weakly computable operation is already computable in the ordinary sense
Effective choice and boundedness principles in computable analysis
No full textIn this paper we study a new approach to classify mathematical theorems ac-
cording to their computational content. Basically, we are asking the question which theorems
can be continuously or computably transferred into each other? For this purpose theorems
are considered via their realizers which are operations with certain input and output data.
The technical tool to express continuous or computable relations between such operations
is Weihrauch reducibility and the partially ordered degree structure induced by it. We have
identified certain choice principles such as co-finite choice, discrete choice, interval choice,
compact choice and closed choice, which are cornerstones among Weihrauch degrees and it
turns out that certain core theorems in analysis can be classified naturally in this structure.
In particular, we study theorems such as the Intermediate Value Theorem, the Baire Cate-
gory Theorem, the Banach Inverse Mapping Theorem, the Closed Graph Theorem and the
Uniform Boundedness Theorem. We also explore how existing classifications of the Hahn–
Banach Theorem and Weak König’s Lemma fit into this picture. Well-known omniscience
principles from constructive mathematics such as LPO and LLPO can also naturally be con-
sidered as Weihrauch degrees and they play an important role in our classification. Based on
thiswe compare the results of our classificationwith existing classifications in constructive and
reverse mathematics and we claim that in a certain sense our classification is finer and sheds
some new light on the computational content of the respective theorems. Our classification
scheme does not require any particular logical framework or axiomatic setting, but it can be
carried out in the framework of classical mathematics using tools of topology, computability
theory and computable analysis. We develop a number of separation techniques based on a
new parallelization principle, on certain invariance properties of Weihrauch reducibility, on
the Low Basis Theorem of Jockusch and Soare and based on the Baire Category Theorem.
Finally, we present a number of metatheorems that allow to derive upper bounds for the
classification of the Weihrauch degree of many theorems and we discuss the Brouwer Fixed
Point Theorem as an example
On the algebraic structure of Weihrauch degrees
Full text linkWe introduce two new operations (compositional products and implication) on Weihrauch degrees, and investigate the overall algebraic structure. The validity of the various distributivity laws is studied and forms the basis for a comparison with similar structures such as residuated lattices and concurrent Kleene algebras. Introducing the notion of an ideal with respect to the compositional product, we can consider suitable quotients of the Weihrauch degrees. We also prove some specific characterizations using the implication. In order to introduce and study compositional products and implications, we introduce and study a function space of multi-valued continuous functions. This space turns out to be particularly well-behaved for effectively traceable spaces that are closely related to admissibly represented spaces
Weihrauch complexity in computable analysis
Full text linkWe provide a self-contained introduction into Weihrauch complexity and its applications to computable analysis. This includes a survey on some classification results and a discussion of the relation to other approaches
- …
