A topological view on algebraic computation models

Neumann, Eike and Pauly, Arno (2017). A topological view on algebraic computation models. Journal of Complexity, in pre ,

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)
Published Online Date: 2017-08-31
Authors: Neumann, Eike
Pauly, Arno

Download

[img]

Version: Accepted Version

Access Restriction: Restricted to Repository staff only until 20 August 2019.

License: Creative Commons Attribution Non-commercial No Derivatives


Export / Share Citation


Statistics

Additional statistics for this record