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.