Neumann, Eike and Pauly, Arno (2018). A topological view on algebraic computation models. Journal of Complexity, 44 , pp. 1-22.
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 |
---|---|
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 |
Publication ISSN: | 0885-064X |
Last Modified: | 30 Oct 2024 08:23 |
Date Deposited: | 07 Sep 2017 09:50 |
Full Text Link: | |
Related URLs: |
http://www.scop ... tnerID=8YFLogxK
(Scopus URL) |
PURE Output Type: | Article |
Published Date: | 2018-02 |
Published Online Date: | 2017-08-31 |
Accepted Date: | 2017-08-02 |
Authors: |
Neumann, Eike
Pauly, Arno |
Download
Version: Accepted Version
License: Creative Commons Attribution Non-commercial No Derivatives
| Preview