Relative computability and uniform continuity of relations
From MaRDI portal
Publication:2930869
DOI10.4115/JLA.2013.5.7zbMATH Open1345.03086arXiv1105.3050OpenAlexW2167006824MaRDI QIDQ2930869FDOQ2930869
Authors: Arno Pauly, Martin Ziegler 
Publication date: 20 November 2014
Published in: Journal of Logic and Analysis (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1105.3050
Recommendations
Logic with extra quantifiers and operators (03C80) Computation over the reals, computable analysis (03D78)
Cites Work
- Dependence logic. A new approach to independence friendly logic
- Title not available (Why is that?)
- How incomputable is finding Nash equilibria?
- Some applications of Henkin quantifiers
- Weihrauch degrees, omniscience principles and weak computability
- Computational complexity on computable metric spaces
- The computable multi-functions on multi-represented sets are closed under programming
- Real computation with least discrete advice: a complexity theory of nonuniform computability with applications to effective linear algebra
- Computability in linear algebra
- Compactness in constructive analysis revisited
- Spaces allowing Type‐2 Complexity Theory revisited
- Title not available (Why is that?)
- Recursive characterization of computable real-valued functions and relations
- The descriptive set-theoretic complexity of the set of points of continuity of a multi-valued function
Cited In (19)
- Continuous and monotone machines
- Computable analysis and notions of continuity in \textsc{Coq}
- The fixed-point property for represented spaces
- New Computational Paradigms
- Game characterizations and lower cones in the Weihrauch degrees
- Towards Computational Complexity Theory on Advanced Function Spaces in Analysis
- Game characterizations and lower cones in the Weihrauch degrees
- Revising type-2 computation and degrees of discontinuity
- Many-one reductions and the category of multivalued functions
- On the continuity of effective multifunctions
- Quantitative continuity and Computable Analysis in Coq
- Computer Science for Continuous Data
- Universal computably enumerable equivalence relations
- Computational benefit of smoothness: parameterized bit-complexity of numerical operators on analytic functions and Gevrey's hierarchy
- A Wadge hierarchy for second countable spaces
- Exploring the beta quadrant
- Quantitative coding and complexity theory of compact metric spaces
- Computations with oracles that measure vanishing quantities
- Uniform continuity of relations and nondeterministic cellular automata
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)
