Affiliations: Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand. {cristian,hertling}@cs.auckland.ac.nz
Note: [] Partially supported by AURC A18/XXXXX/62090/F3414075, 1997.
Note: [] Supported by DFG Research Grant No. HE 2489/2-1.
Abstract: How fast can one approximate a real by a computable sequence of rationals? Rather surprisingly, 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 also show that one can computably approximate any computable real 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.
Keywords: Computable reals, random reals, approximations, program-size complexity, information content
