Back to search

McMaster University

Characterization of Semicomputable Sets, and Computable Partial Functions, on the Real Plane

Abstract

dc:description.abstract

(1) Characterizations of semicomputable subsets of the Real Plane as unions of effective infinite sequences of "elementary" open sets. This developed from Bo Xie's MSc thesis (2004) on semicomputable subsets of R, where the elementary sets are simply open (rational or algebraic) intervals. This is generalized to two dimensions by taking elementary sets to be basic open semalgebraic sets. Three structure theorems are derived, based on computability by various forms of the 'whiles' programming language. By means of the cell decomposition theorem, variants of these structure theorem are derived, with "basic open semialgebraic sets" replaced by "connected open semialgebraic sets". (2) Equivalence of computability models for partial functions on the Real Plane. This developed from the research in my Msc thesis (2007) for partial functions f on R, in which four models of computability (including Grzegorczyk-Lacombe (GL) computability, tracking computability, and multi-polynomial approximability) were shown to be equivalent, under two global assumptions: (i) the domain of f is the union of an effective exhaustion of finite unions of "elementary" open sets, (ii) f is effectively locally uniformly continuous w.r.t this exhaustion. This thesis extends this study to functions on the Real Plane. For functions on R, the elementary sets were simply rational open intervals. For functions on the Real Plane (as in this thesis), the appropriate elementary sets turn out to be bounded, connected basic open semialgebraic subsets of the plane. The most interesting of the equivalence proofs is in the direction "GL comp. => multipolynomial approx". Here the function f, defined on an elementary set, is first effectively extended to a GL-computable function on a rectangle, and then approximated by a sequence of polynomials, using an effective version of the Weierstrass theorem in 2 dimensions. The cell decomposition theorem is again used here, to justify the algorithm extending the domain of f to a rectangle. It is conjectured that the two global conditions are satisfied by all elementary functions of two real variables.

Degree

thesis:*
Department dc:contributor.department
Computer Science
Year dc:date.issued
2014

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Fu, Ming Quan
Advisor dc:contributor.advisor
  • Zucker, Jeffery

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-18
Source record
OAI-PMH GetRecord
related terms
citation

Fu, Ming Quan. Characterization of Semicomputable Sets, and Computable Partial Functions, on the Real Plane. 2014. http://hdl.handle.net/11375/16066