[FOM] Status of Quantum Computing - Omega Wellfoundedness

[Axiomize@aol.com]

> I divided the natural numbers into sets of three numbers --
> {2,1,3}, {4,5,7}, {6,9,11}, {8,13,15}, {10,17,19}, {12,21,23}, ...,
> so I got a well-defined probability of 1/3 of a number being even.

Touché.  (This is similar to the principle that I used in my non-converging 
halting probability program P, allocating the halts and loops to oscillate 
between 1/3 and 2/3.)  So even simple integer parity probability is difficult 
to formalize - even more so for halting probability.

> The actual value of Omega certainly depends on what probabilities are
> assigned to what Turing machines.

I take "random" to mean a uniform distribution.  Why have it any other way?  
We still haven't computed that using coin flips (nor even simple integer 
parity probability.)

> Once those probabilities are set, Omega is certainly well-defined.

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?

For any 0<k1<k2<1 there is a representation of Turing Machines for which 
Omega is in the interval (k1,k2):

Use symbol 0 for "end" (the programs are 1*0) so that the probabilities 
assigned to individual Turing Machines are 1/2, 1/4 , 1/8, . . .  Let M be 
the length of the maximum leading substring of bits common to the binary 
expansions of k1 and k2.  Code the first M+1 Turing Machines to halt (1) or 
loop (0) according to the first M+1 bits of k2.  The M+1th Turing Machine 
will halt, keeping Omega > k1.  Code Turing Machines M+2 through the position 
of the first bit 1 in k2 after position M+1 to loop, keeping Omega < k2.  
Then Omega is between k1 and k2, the actual value depending on the halting 
behavior of the Turing Machines after that point.

Omega can be negligibly close to any given probability by choice of 
representation.

Is there significance to any particular representation (and thus any 
particular value of Omega)?

> But for the purposes of our discussion, it does not really matter how they 
are set;
> whatever Omega we get will be equivalent to the Halting Problem.

(That is assuming that no subset of these probabilities has the same sum as 
any other subset.)

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)?

> Steve

Charlie Volkstorf
Cambridge, MA