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.