Back to search

McMaster University

Notions of Semicomputability in Topological Algebras over the Reals

Abstract

dc:description.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 a generalisation of computability theory over total abstract algebras, using for instance the model of \While\ computation. We present a number of results relating to computation on topological partial algebras, again using \While\ computation. We consider several results from the classical theory in the context of topological algebra of the reals: closure of semicomputable sets under finite union (Chapter \ref{chap:results1} Theorem \ref{thm:union_While_scomp_not_While_scomp}, p.\pageref{thm:union_While_scomp_not_While_scomp}), the equivalence of semicomputable and projectively (semi)computable sets (Chapter \ref{chap:results2} Theorem \ref{thm:proj_while_equivalents}, p.\pageref{thm:proj_while_equivalents}), and Post's Theorem (i.e.~a set is computable iff both it and its complement are semicomputable) (Appendix \ref{appendix:posts_theorem} Theorem \ref{thm:posts_general}, p.\pageref{thm:posts_general}). This research has significance in the field of scientific computation, which is underpinned by computability on the real numbers. We will consider a ``continuity principle", which states that computability should imply continuity; however, equality, order, and other total boolean-valued functions on the reals are clearly discontinuous. As we want these functions to be basic for the algebras under consideration, we resolve this incompatibility by redefining such functions to be partial, leading us to consider topological partial algebras.

Degree

thesis:*
Department dc:contributor.department
Computing and Software
Year dc:date.issued
2015

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Armstrong, Mark
Advisor dc:contributor.advisor
  • Zucker, Jeffery

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Armstrong, Mark. Notions of Semicomputability in Topological Algebras over the Reals. 2015. http://hdl.handle.net/11375/18334