Journal article 1181 views 188 downloads
A topological view on algebraic computation models
Journal of Complexity, Volume: 44, Pages: 1 - 22
Swansea University Authors:
Eike Neumann, Arno Pauly
-
PDF | Accepted Manuscript
Released under the terms of a Creative Commons Attribution Non-Commercial No Derivatives License (CC-BY-NC-ND).
Download (520.52KB)
DOI (Published version): 10.1016/j.jco.2017.08.003
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 conseque...
| Published in: | Journal of Complexity |
|---|---|
| ISSN: | 0885-064X |
| Published: |
Elsevier BV
2018
|
| Online Access: |
Check full text
|
| URI: | https://cronfa.swan.ac.uk/Record/cronfa37369 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| 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. |
|---|---|
| Keywords: |
TTE, Computable analysis, BSS-machines |
| College: |
Faculty of Science and Engineering |
| Start Page: |
1 |
| End Page: |
22 |