Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 1998

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Computable approximations of reals: an information-theoretic analysis

Calude C.S., Hertling P.H.

Fundamenta Informaticae

1998

Vol. 33, nr 2

105-120

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.