# 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
- Disciplines

## 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.