Abstract:
On countable structures computability is usually introduced via numberings. For
uncountable structures whose cardinality does not exceed the cardinality of the continuum the same can be done via representations. Which representations are appropriate for doing real number computations? We show that with respect to computable
equivalence there is one and only one equivalence class of representations of the real
numbers which make the basic operations computable. This characterizes the real
numbers in terms of the theory of effective algebras or computable structures, and is
reflected by observations made in real number computer arithmetic. We also give further evidence for the well-known non-appropriateness of the representation to some
base b by proving that strictly less functions are computable with respect to these
representations than with respect to a standard representation of the real numbers.
Furthermore we consider basic constructions of representations and the countable
substructure consisting of the computable elements of a represented, possibly uncountable structure. For countable structures we compare effectivity with respect to
a numbering and effectivity with respect to a representation. Special attention is paid
to the countable structure of the computable real numbers.