[FOM] Status of Quantum Computing - Omega Wellfoundedness
Axiomize@aol.com
Axiomize at aol.com
Tue Oct 22 17:17:45 EDT 2002
> 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
More information about the FOM
mailing list