[FOM] Status of Quantum Computing - Omega Wellfoundedness

[Miguel A. Lerma]

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