[FOM] normal numbers

[Rupert McCallum]

I have a question about the definition of normal numbers.

Here we have defined them as numbers in which the frequency with which
finite sequences of digits occur are the same as would be expected of
random distribution. I have seen elsewhere the claim that sometimes
further conditions are imposed, to the effect that the covariances
between the occurrences of pairs of finite sequences of digits are also
what would be expected of random distribution.

Is there a generally agreed-upon definition of normal number?

--- Veronica Becher <vbecher at dc.uba.ar> wrote:

> 
> 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.
> ------------------------------------------------------------------
> 
> 
> 
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
> 



       
____________________________________________________________________________________
Take the Internet to Go: Yahoo!Go puts the Internet in your pocket: mail, news, photos & more. 
http://mobile.yahoo.com/go?refer=1GNXIC