Affordable Access

Publisher Website

Characterizations of semicomputable sets of real numbers

The Journal of Logic and Algebraic Programming
DOI: 10.1016/j.jlap.2013.11.001
  • Computability On Reals
  • Computability On Topological Algebras
  • Engeler'S Lemma
  • Semicomputable Sets Of Reals
  • Computer Science
  • Mathematics


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.