A topological view on algebraic computation models

Abstract

We investigate the topological aspects of some algebraic computation models, in particular the BSS-model. Our results can be seen as bounds on how different BSS-computability and computability in the sense of computable analysis can be. The framework for this is Weihrauch reducibility. As a consequence of our characterizations, we establish that the solvability complexity index is (mostly) independent of the computational model, and that there thus is common ground in the study of non-computability between the BSS and TTE setting.

Publication DOI: https://doi.org/10.1016/j.jco.2017.08.003
Divisions: Engineering & Applied Sciences > Computer Science
Additional Information: © 2017, Elsevier. Licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International http://creativecommons.org/licenses/by-nc-nd/4.0/
Uncontrolled Keywords: Analytic machine,BSS-machine,Computable analysis,Effective DST,Solvability complexity index,Weihrauch reducibility,Algebra and Number Theory,Statistics and Probability,Numerical Analysis,Control and Optimization,Applied Mathematics
Full Text Link:
Related URLs: http://www.scop ... tnerID=8YFLogxK (Scopus URL)
PURE Output Type: Article
Published Date: 2017-08-31
Published Online Date: 2017-08-31
Accepted Date: 2017-08-02
Authors: Neumann, Eike
Pauly, Arno

Export / Share Citation


Statistics

Additional statistics for this record