Computable approximations of reals: an information-theoretic analysis

• Autorzy: Calude C.S. , Hertling P.H.
• Języki publikacji: EN

Abstrakty

EN

How fast can one approximate a real by a computable sequence of rationales? 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 rationales (this is the case, for example, for Chaitin's W 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 computable sequence of rationals which converges (monotonically) to a computable real.

Słowa kluczowe

EN

computable real; random real; approximation; program-size complexity; information content

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 1998
• Tom: Vol. 33, nr 2
• Strony: 105--120
• Opis fizyczny: bibliogr. 17 poz.

Twórcy

autor

Calude C.S.

autor

Hertling P.H.

• Department of Computer Science University of Auckland Private Bag 92019, Auckland, New Zeland,