A topological view on algebraic computation models

2016/02/25 by Eike Neumann, Neumann, Eike, Arno Pauly +1 · 1 citation
Computer Science · #Computability, Logic, AI Algorithms #F.1.1 #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Topological and Geometric Data Analysis #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1602.08004

openalex publication_date 2016/02/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Cited by

• The Myhill isomorphism theorem does not generalize much

Related

• Topological Characterization of Task Solvability in General Models of Computation
• On the computational properties of the Baire Category Theorem
• Unifying lower bounds for algebraic machines, semantically
• Computable quotient presentations of models of arithmetic and set theory
• Lawvere-Tierney topologies for computability theorists