Relative computability and uniform continuity of relations
From MaRDI portal
Abstract: A type-2 computable real function is necessarily continuous; and this remains true for relative, i.e. oracle-based computations. Conversely, by the Weierstrass Approximation Theorem, every continuous f:[0,1]->R is computable relative to some oracle. In their search for a similar topological characterization of relatively computable multivalued functions f:[0,1]=>R (aka relations), Brattka and Hertling (1994) have considered two notions: weak continuity (which is weaker than relative computability) and strong continuity (which is stronger than relative computability). Observing that uniform continuity plays a crucial role in the Weierstrass Theorem, we propose and compare several notions of uniform continuity for relations. Here, due to the additional quantification over values y in f(x), new ways of (linearly) ordering quantifiers arise, yet none of them turn out as satisfactory. We are thus led to a notion of uniform continuity based on the Henkin Quantifier; and prove it necessary for relative computability. In fact iterating this condition yields a strict hierarchy of notions each necessary, and the omega-th level also sufficient, for relative computability.
Recommendations
Cites work
- Compactness in constructive analysis revisited
- Computability in linear algebra
- Computational complexity on computable metric spaces
- Dependence logic. A new approach to independence friendly logic
- How incomputable is finding Nash equilibria?
- scientific article; zbMATH DE number 1163935 (Why is no real title available?)
- scientific article; zbMATH DE number 1460545 (Why is no real title available?)
- Real computation with least discrete advice: a complexity theory of nonuniform computability with applications to effective linear algebra
- Recursive characterization of computable real-valued functions and relations
- Some applications of Henkin quantifiers
- Spaces allowing Type‐2 Complexity Theory revisited
- The computable multi-functions on multi-represented sets are closed under programming
- The descriptive set-theoretic complexity of the set of points of continuity of a multi-valued function
- Weihrauch degrees, omniscience principles and weak computability
Cited in
(19)- Game characterizations and lower cones in the Weihrauch degrees
- Quantitative coding and complexity theory of compact metric spaces
- The fixed-point property for represented spaces
- Universal computably enumerable equivalence relations
- Many-one reductions and the category of multivalued functions
- Towards Computational Complexity Theory on Advanced Function Spaces in Analysis
- Computations with oracles that measure vanishing quantities
- Computational benefit of smoothness: parameterized bit-complexity of numerical operators on analytic functions and Gevrey's hierarchy
- On the continuity of effective multifunctions
- Revising type-2 computation and degrees of discontinuity
- A Wadge hierarchy for second countable spaces
- Computable analysis and notions of continuity in \textsc{Coq}
- Continuous and monotone machines
- Exploring the beta quadrant
- Game characterizations and lower cones in the Weihrauch degrees
- Uniform continuity of relations and nondeterministic cellular automata
- New Computational Paradigms
- Quantitative continuity and Computable Analysis in Coq
- Computer Science for Continuous Data
This page was built for publication: Relative computability and uniform continuity of relations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2930869)
