Journal article 1230 views 200 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 |