Characterizations of semicomputable sets of real numbers

• We work in a topological partial algebra R over the reals.
• Semicomputable sets of reals are halting sets of ‘While’ programs on R.
• We characterize such sets as unions of rational or algebraic intervals.
• We must augment ‘While’ with strong OR and/or an existential quantifier over N.

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 OROR operator, and for equivalences (ii) and (iii) it must be further augmented by a strong existential quantifier over the naturals (While∃NWhile∃N).We also show that the class of While∃NWhile∃N semicomputable relations on reals is closed under projection. The proof makes essential use of the continuity of the operations of the algebra.