• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Notions of Semicomputability in Topological Algebras over the Reals

Armstrong, Mark 11 1900 (has links)
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. / Thesis / Master of Computer Science (MCS) / We investigate to what extent certain well-known results of classical computability theory on the natural numbers hold in the context of generalised computability theories on the real numbers.

Page generated in 0.0886 seconds