Bo (Tyler) Xie:   MSc, August 2004.
Characterisations of Semicomputable Sets of Real Numbers.

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 algebraic open intervals;
(iii) unions of effective sequences of rational open intervals;

For the equivalence (i), the While language must be augmented by a strong (Kleene) OR operator, and for equivalences (ii) and (iii) it must be further augmented by a strong existential quantifier over the naturals (ExistN).

We also show that the class of While+(ExistN) semicomputable relations on reals is closed under projections.
The proof makes essential use of the continuity of the operations of the algebra.