No Cover Image

Journal article 347 views 19 downloads

A topological view on algebraic computation models / Eike Neumann; Arno Pauly

Journal of Complexity, Volume: 44, Pages: 1 - 22

Swansea University Author: Arno, Pauly

  • models-finalversion.pdf

    PDF | Accepted Manuscript

    Released under the terms of a Creative Commons Attribution Non-Commercial No Derivatives License (CC-BY-NC-ND).

    Download (520.52KB)

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...

Full description

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
Start Page: 1
End Page: 22