Abstract:
How fast can one approximate a real by a computable sequence of rationals?
We show that the answer to this question depends very much on the information
content in the finite prefixes of the binary expansion of the real. Computable reals,
whose binary expansions have a very low information content, can be approximated
(very fast) with a computable convergence rate. Random reals, whose binary expansions
contain very much information in their prefixes, can be approximated only
very slowly by computable sequences of rationals (this is the case, for example, for
Chaitin's Ω numbers) if they can be computably approximated at all.
We show that one can computably approximate any computable real also very
slowly, with a convergence rate slower than any computable function. However, there
is still a large gap between computable reals and random reals: any computable sequence
of rationals which converges (monotonically) to a random real converges
slower than any computable sequence of rationals which converges (monotonically)
to a computable real.