Affiliations: [a] Department of Computing & Software, McMaster University, Hamilton, ON L8S 4K1, Canada. armstmp@mcmaster.ca | [b] Department of Computing & Software, McMaster University, Hamilton, ON L8S 4K1, Canada. zucker@mcmaster.ca
Abstract: Several results from classical computability theory (computability over discrete structures such as the natural numbers and strings over finite alphabets, due to Turing, Church, Kleene and others) have been shown to hold for generalisations of computability theory over total abstract algebras, using a computation model of a high level imperative (While) language. We present a number of results relating to computation on topological partial algebras using an abstract model of computation, While, based on high level imperative languages. We investigate the validity of several results from the classical theory in the context of topological algebras on the reals: closure of semicomputable sets under finite union, the equivalence of semicomputable and projectively (semi)computable sets, and Post’s Theorem. This research has significance in the field of scientific computation, which is underpinned by computability on the real numbers. By the Continuity Principle, computability of functions implies their continuity. Since equality, order, and other total boolean-valued functions on the reals are clearly discontinuous, we resolve this incompatibility by redefining such functions to be partial, leading us to consider topological partial algebras.
Keywords: Generalised computability, computability on topological algebra, computability on the reals
DOI: 10.3233/COM-180087
Journal: Computability, vol. 8, no. 1, pp. 1-26, 2019
