[FOM] normal numbers/Chaitin number

[Jan Pax]

I would like to ask which is the best currently known lower bound
for the absolutely normal number Chaitin's constant Omega.
I'm not sure if this question makes sense since Omega's value may
depend on the chosen coding of Turing machines as 0-1 strings.
Is there any standard coding which makes Omega unique?
Thank you, JP


>  
>  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
>  
>  
>