bs@faron.UUCP (Robert D. Silverman) (01/21/86)
Does anyone have any references concerning the (relatively) new constant called omega? Omega is the exact probability that a random input tape fed to a deterministic Turing machine will cause the machine to halt. Obviously this probability is very close to one because a random input tape will have a high probability of having an error in it that would cause a halt. I believe that it has been shown that omega is not computable. Bob Silverman
ags@pucc-h (Dave Seaman) (01/23/86)
In article <440@faron.UUCP> bs@faron.UUCP (Robert D. Silverman) writes: >Does anyone have any references concerning the (relatively) new constant >called omega? Omega is the exact probability that a random input tape >fed to a deterministic Turing machine will cause the machine to halt. One of Martin Gardner's last columns for Scientific American contained a discussion of this constant. I believe the definition is somewhat more complex than you indicate, since it consists of powers of two summed in such a way that, if you knew the exact value, you could decode it to determine whether any particular input tape will cause the machine to halt. >I believe that it has been shown that omega is not computable. Obviously. -- Dave Seaman pur-ee!pucc-h!ags
ark@alice.UucP (Andrew Koenig) (01/23/86)
> Does anyone have any references concerning the (relatively) new constant > called omega? Omega is the exact probability that a random input tape > fed to a deterministic Turing machine will cause the machine to halt. > Obviously this probability is very close to one because a random input > tape will have a high probability of having an error in it that would > cause a halt. > > I believe that it has been shown that omega is not computable. Surely the definition as stated is incomplete, because it says nothing about the particular Turing machine, or about the distribution of the possible input tapes. I have the strong suspicion, however, that any reasonable filling-in of this definition would result in a value that is not computable.
bs@faron.UUCP (Robert D. Silverman) (01/24/86)
> > Does anyone have any references concerning the (relatively) new constant > > called omega? Omega is the exact probability that a random input tape > > fed to a deterministic Turing machine will cause the machine to halt. > > Obviously this probability is very close to one because a random input > > tape will have a high probability of having an error in it that would > > cause a halt. > > > > I believe that it has been shown that omega is not computable. > > Surely the definition as stated is incomplete, because it says nothing > about the particular Turing machine, or about the distribution of the > possible input tapes. I have the strong suspicion, however, that > any reasonable filling-in of this definition would result in a value > that is not computable. You're correct, I should have been more specific. There is, I believe a family of such constants which depend upon the number of states of the Turing machine. The input tapes are assumed to have the following distributions: 1. The length of the tape is uniformly distributed over [1,infinity). This is generally called an 'improper' or 'diffuse' distribution in Bayesian statitistics. Its measure over any fixed interval is zero, but its measure over [1,infinity) is 1. More formally: Probability(length = N) = lim 1/n as n -> infinity for any N sum( P(length = N) ) for N = 1 to infinity is then just: lim n*(1/n) as n -> infinity which equals one. Basically all this says is that the input tape length is finite and all lengths have the same probability. 2. Any given position on the tape has Prob(position is 1) = 1/2 Prob(position is 0) = 1/2
mendel@utcsri.UUCP (Alberto Mendelzon) (01/27/86)
Consider a universal Turing machine that is fed a random sequence of bits, e.g. by flipping a coin whenever the machine requests another bit. Omega was defined by Gregory Chaitin as the probability that the machine will eventually halt. The exact value of omega depends on the particular universal Turing machine. Martin Gardner's relevant column in Scientific American appeared in November 1979 (Vol 241, No. 5). -- Alberto Mendelzon utcsri!mendel mendel@toronto