Bo (Tyler) Xie: MSc, August 2004.
Characterisations of Semicomputable Sets
of Real Numbers.
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
(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.
makes essential use of the continuity of the operations of