A topological view on algebraic computation models

Eike Neumann; Arno Pauly

doi:10.1016/j.jco.2017.08.003

A topological view on algebraic computation models

Eike Neumann, Arno Pauly^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	1-22
Number of pages	22
Journal	Journal of Complexity
Volume	44
Early online date	31 Aug 2017
DOIs	https://doi.org/10.1016/j.jco.2017.08.003
Publication status	Published - Feb 2018

Bibliographical note

Keywords

Analytic machine
BSS-machine
Computable analysis
Effective DST
Solvability complexity index
Weihrauch reducibility

Access to Document

10.1016/j.jco.2017.08.003

Topological view on algebraic computation models
© 2017, Elsevier. Licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International http://creativecommons.org/licenses/by-nc-nd/4.0/
Accepted author manuscript, 551 KBLicence: CC BY-NC-ND 3.0

Cite this

@article{353ed3c166644abc9dddaffbca2bfbe1,

title = "A topological view on algebraic computation models",

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 = "Analytic machine, BSS-machine, Computable analysis, Effective DST, Solvability complexity index, Weihrauch reducibility",

author = "Eike Neumann and Arno Pauly",

note = "{\textcopyright} 2017, Elsevier. Licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International http://creativecommons.org/licenses/by-nc-nd/4.0/ ",

year = "2018",

month = feb,

doi = "10.1016/j.jco.2017.08.003",

language = "English",

volume = "44",

pages = "1--22",

journal = "Journal of Complexity",

issn = "0885-064X",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - A topological view on algebraic computation models

AU - Neumann, Eike

AU - Pauly, Arno

PY - 2018/2

Y1 - 2018/2

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

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

KW - Analytic machine

KW - BSS-machine

KW - Computable analysis

KW - Effective DST

KW - Solvability complexity index

KW - Weihrauch reducibility

UR - http://www.scopus.com/inward/record.url?scp=85029651788&partnerID=8YFLogxK

U2 - 10.1016/j.jco.2017.08.003

DO - 10.1016/j.jco.2017.08.003

M3 - Article

SN - 0885-064X

VL - 44

SP - 1

EP - 22

JO - Journal of Complexity

JF - Journal of Complexity

ER -

A topological view on algebraic computation models

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this