[FOM] normal numbers/Chaitin number

[Hector Zenil]

The calculation of Omega is dependable on the chosen universal Turing
machine so that's the reason for which the Omega number is not a
constant as many sources use to refer to. Omega is in fact a set of
maximal information and algorithmical random numbers which coincide to
be those strongly noncomputable--actually noncomputables by definition
since their digits depend on the halting probability of the universal
TM.

However, Greg Chaitin has suggested a way to calculate his Omega
number and Cristian S. Calude and Michael J. Dinneen wrote a paper
entitled "Exact Approximations of Omega Numbers"
http://www.cs.auckland.ac.nz/CDMTCS//researchreports/293crismjd.pdf
in which, by means of register machine programs computed by a
prefix-free universal Turing machine they provide the exact
approximations of two Omega numbers of the same prefix-free Turing
machine. The 43 exact bits for the base 16 machine and 40 exact bits
for the base 2 machine are.

00010 00000 01000 01010 01110 11100 01000 00101 110
00010 00000 01000 01010 01110 11100 00111 11010
respectively. That is a standard coding but it is still dependable on
the chosen base of even after fixing the Turing machine itself.

Recently Greg Chaitin was honored in the University of Vermont during
the NKS 2007 WolframScience Conference because of his 60th.
anniversary. He was given a medallion with the Omega number and the 40
first digits from Calude et al. paper printed on it in celebration of
his contributions to math and computer science.

Hector



Hector Zenil-Chavez
hector.zenil-chavez at malix.univ-paris1.fr
Université de Lille I (LIFL)
Université de Paris I (Pantheon-Sorbonne) (IHPST)


On 7/20/07, Jan Pax <pax0 at seznam.cz> wrote:
> 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
> >
> >
> >
>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>