[FOM] Status of Quantum Computing - Omega Wellfoundedness

[Axiomize@aol.com]

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

> Omega is . . . Chaitin-random, Solovay-random, Martin-Lof-random.
> See for instance:  Antonin Kucera and Theodore A. Slaman:
> "Randomness and Recursive Enumerability", SIAM J. Comput, Vol.31,
> No.1, pp. 199-211.

These three sets (definitions) are equivalent (theorems 1.3 and 1.9 in the 
cited article.)  Any property true of all values of Omega will hold for Ru in 
particular.

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

Let np(L) = the number of programs of length L.  Then for any positive N, if 
np(L)=0 for all L <= N+1 and np(L)=1 for all L > N+1, then the first N bits 
of Omega are zero, since Omega < sum [L>0] np(L)/(2^L) = sum[L>N+1] 1/(2^L) = 
1/(2^(N+1)).

(This is a constructive proof of a special case of my earlier proposition: 
Every interval within (0,1) contains an Omega, i.e., for all 0<k1<k2<1, there 
is an Omega in (k1,k2), where, here, k1=0 and k2=1/(2^(N+1)).  This is what I 
meant by Omega being arbitrary.  It can also be shown for certain unbounded 
functions np.  Ru is effectively np(L)=1 for all L.)

Thus Ru requires log_2(N) + c1 bits, while Omega requires between c2 and N + 
c2 bits (depending on the representation for Turing Machines being used.)  
Which has greater complexity depends on whether "complexity" is defined in 
terms of the minimum or the maximum.  Ru has the advantage that its 
complexity is independent of the lengths of programs, i.e., function np.  (Ru 
is what Turing was referring to by "On Computable Numbers".)

> Miguel A. Lerma

Charlie Volkstorf
Cambridge, MA