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

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.