[FOM] Status of Quantum Computing - Omega Wellfoundedness

[Miguel A. Lerma]

Charlie Volkstorf wrote:
 > Is "the probability of a Turing Machine halting" (assuming uniform 
 > distribution of Turing Machines) well-defined?
 > Is the "probability of program P halting" (assuming uniform distribution of 
 > N) well-defined?

I do not think so, that probability would be defined as a limit that
(as in your example) may not exist.  But in the definition of
Chaitin's Omega number the halting probability is the limit of an
increasing (and bounded) sequence of rationals, which always exists. 
In fact that sequence of rationals can be chosen to be recursive. 
Let S(n,t) be the set of programs of size not greater than n that 
halt in at most t steps, and define

   P(n,t) = sum of 2^(-|p|) for p in S(n,t) 

where |p| = size of program p.  Then f(n) = P(n,n) is increasing and
Omega = lim f(n) as n -> infinity.  Furthermore, f(n) is recursive -
think of a universal Turing machine that for each n runs n steps of
all programs of size not greater than n and outputs P(n,n).

Real numbers than can be approximated by an increasing, recursive
sequence of rationals are called "recursively enumerable", so
Chaitin's Omega numbers are r.e.  Not all r.e. real numbers in (0,1)
are Omega numbers (obviously, since Omega numbers are uncomputable and
there are many computable r.e. numbers), but there is a particular
class of r.e. real numbers called Omega-like numbers (in (0,1)) which
at the end turned out to be identical to the class of Omega numbers.
Their definition can be stated as follows.  A r.e. real alpha
"dominates" another r.e. real beta if there are recursive,
non-decreasing rational sequences a_n and b_n and a constant c such
that lim a_n = a, lim b_n = b, and c(alpha - a_n) >= beta - b_n.  
A r.e. real is called Omega-like if it dominates every r.e. real, i.e.,
Omega-like reals are the maximal elements respect to the dominance
relation (the minimal ones are the recursive [or computable] reals).

Informally, beta dominates alpha means that beta is more random than
alpha.  Omega-like numbers are the most random of all (among
r.e. reals), and they coincide with Omega numbers (in (0,1)).

 > How is Omega different (formally, please) from any other encoding of the 
 > halting predicate into a real number (e.g. Marvin Minsky, "Computation: 
 > Finite and Infinite Machines", 1967, p. 159)?

In the extremely compact way in which the information is packed in
Chaitin's Omega number.  Omega is algorithmically incompressible,
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.


Miguel A. Lerma