[FOM] normal numbers

[Veronica Becher]

We (Santiago Figueira and I) would like to post 
the following answer to one of the lasts posts 
regarding absolutely normal numbers

Here are known specific examples of absolutely normal numbers:

1) Sierpinski 1916 gave a construction (it is an infimum of some
infinite unions and intersections, hence not an algorithm). A
computable reformulation of Sierpinski's number was given by us
in 2002. The time complexity of outputting n symbols of the
fractional expansion is double exponential in n.

Verónica Becher, Santiago Figueira. An example of a computable
absolutely normal number.  Theoretical Computer Science 270,
947­958, 2002. http://dx.doi.org/10.1016/S0304-3975(01)00170-0

2) Turing itself gave an algorithm (unpublished, probably in
1935) answering the then outstanding question of whether there
were constructive methods to produce abs. normal numbers. Our
reconstruction of Turing's:

    V. Becher, S. Figueira and R. Picchi.
    Turing’s unpublished algorithm for normal numbers.
    Theoretical Computer Science, 377 (1-3):126-138, 2007.
    http://dx.doi.org/10.1016/j.tcs.2007.02.022

The algorithm outputs an abs. normal real number with an explicit
convergence to normality. The time complexity to outputting the
first n symbols of the fractional expansion is double exponential
in n.

Turing's algorithm allows to generate abs. normal numbers from
arbitrary oracles. Varying oracles one obtains different abs.
normal numbers (in fact, Lebesgue measure of the set of
obtainable numbers is arbitrarily close to one).

3) There are absolutely normal numbers with lower time
complexity, but still not computationally feasible. A simple
exponential complexity bound for computing an absolutely normal
number follows from the work of Ambos-Spies, Terwjin and Zheng
(1997) on reals that are random with respect to polynomial-time
martingales.

4) Martin-L"of random reals, like Chaitin's Omega number, are all
absolutely normal but not computable.
------------------------------------------------------------------