Comparing representations for function spaces in computable analysis
From MaRDI portal
Publication:1635809
DOI10.1007/S00224-016-9745-6zbMATH Open1436.03241DBLPjournals/mst/PaulyS18arXiv1512.03024OpenAlexW2577444373WikidataQ59602648 ScholiaQ59602648MaRDI QIDQ1635809FDOQ1635809
Authors: Arno Pauly, Florian Steinberg 
Publication date: 1 June 2018
Published in: Theory of Computing Systems (Search for Journal in Brave)
Abstract: This paper compares different representations (in the sense of computable analysis) of a number of function spaces that are of interest in analysis. In particular subspace representations inherited from a larger function space are compared to more natural representations for these spaces. The formal framework for the comparisons is provided by Weihrauch reducibility. The centrepiece of the paper considers several representations of the analytic functions on the unit disk and their mutual translations. All translations that are not already computable are shown to be Weihrauch equivalent to closed choice on the natural numbers. Subsequently some similar considerations are carried out for representations of polynomials. In this case in addition to closed choice the Weihrauch degree LPO* shows up as the difficulty of finding the degree or the zeros. As a final example, the smooth functions are contrasted with functions with bounded support and Schwartz functions. Here closed choice on the natural numbers and the lim degree appear.
Full work available at URL: https://arxiv.org/abs/1512.03024
Recommendations
computable analysispolynomialsanalytic functionclosed choicefinitely many mindchangesWeihrauch reduction
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Computability and Noncomputability in Classical Analysis
- Weihrauch degrees, omniscience principles and weak computability
- Computable invariance
- On the (semi)lattices induced by continuous reducibilities
- Effective Choice and Boundedness Principles in Computable Analysis
- Effective Borel measurability and reducibility of functions
- Closed choice and a uniform low basis theorem
- Title not available (Why is that?)
- Computability theory of generalized functions
- Real computation with least discrete advice: a complexity theory of nonuniform computability with applications to effective linear algebra
- Computational benefit of smoothness: parameterized bit-complexity of numerical operators on analytic functions and Gevrey's hierarchy
- Extended admissibility.
- IS WAVE PROPAGATION COMPUTABLE OR CAN WAVE COMPUTERS BEAT THE TURING MACHINE?
- The Wave Equation with Computable Initial Data Whose Unique Solution Is Nowhere Computable
- Finite choice, convex choice and finding roots
- Non-deterministic computation and the Jayne-Rogers theorem
- A topological view on algebraic computation models
- A constructive algorithm for finding the exact roots of polynomials with computable real coefficients.
- Probabilistic computability and choice
- Reverse mathematics of matroids
- Title not available (Why is that?)
- Descriptive set theory in the category of represented spaces
- Weihrauch-completeness for layerwise computability
- Representations of analytic functions and Weihrauch degrees
- On the topological aspects of the theory of represented spaces
Cited In (10)
- Computable analysis and notions of continuity in \textsc{Coq}
- Comparison of Some Reduced Representation Approximations
- Complexity theory for spaces of integrable functions
- Representations and evaluation strategies for feasibly approximable functions
- Representations of analytic functions and Weihrauch degrees
- Total representations
- Title not available (Why is that?)
- Title not available (Why is that?)
- Weihrauch Complexity in Computable Analysis
- On Computational Constructions in Function Spaces
This page was built for publication: Comparing representations for function spaces in computable analysis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1635809)
