[FOM] Status of Quantum Computing - Omega Wellfoundedness
Miguel A. Lerma
mlerma at math.northwestern.edu
Sun Oct 27 23:21:43 EST 2002
Charlie Volkstorf wrote
> > Minsky's Ru number is obviously a particular case of Chaitin's
> > Omega number, but I am not sure whether every Omega number
> > is a Ru number.
>
> Since Ru contains more information than Omega in general, then I would
> conclude that they are different sets of numbers.
People who know more than me on this matters have made me notice that
there is an additional condition in the definition of Chaitin's Omega
number not fulfilled by Ru: besides being universal the underlying
Turing machine must also be "optimal". In terms of programs we need
any programming language to be translatable into the language of our
machine with O(1) overhead.
Ru has smaller complexity than Omega. We can compute its N first
digits just by knowing how many of its digits are 1, since we can
wait until the required number of computations terminate. So log_2(N)
bits are enough. For computing the first N digits of Omega, however,
we need at least N - c bits for some constant c.
Miguel A. Lerma
More information about the FOM
mailing list