Affordable Access

Publisher Website

Characterizations of semicomputable sets of real numbers

Authors
Journal
The Journal of Logic and Algebraic Programming
1567-8326
Publisher
Elsevier
Identifiers
DOI: 10.1016/j.jlap.2013.11.001
Keywords
  • Computability On Reals
  • Computability On Topological Algebras
  • Engeler'S Lemma
  • Semicomputable Sets Of Reals
Disciplines
  • Computer Science
  • Mathematics

Abstract

Abstract We give some characterizations of semicomputability of sets of reals by programs in certain While programming languages over a topological partial algebra of reals. We show that such sets are semicomputable if and only if they are one of the following:(i) unions of effective sequences of disjoint algebraic open intervals; (ii) unions of effective sequences of rational open intervals; (iii) unions of effective sequences of algebraic open intervals. For the equivalence (i), the While language must be augmented by a strong OR operator, and for equivalences (ii) and (iii) it must be further augmented by a strong existential quantifier over the naturals (While∃N). We also show that the class of While∃N semicomputable relations on reals is closed under projection. The proof makes essential use of the continuity of the operations of the algebra.

There are no comments yet on this publication. Be the first to share your thoughts.