Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site faron.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!bellcore!decvax!linus!faron!bs
From: bs@faron.UUCP (Robert D. Silverman)
Newsgroups: net.math
Subject: Re: Omega
Message-ID: <446@faron.UUCP>
Date: Thu, 23-Jan-86 22:25:07 EST
Article-I.D.: faron.446
Posted: Thu Jan 23 22:25:07 1986
Date-Received: Sat, 25-Jan-86 07:49:55 EST
References: <440@faron.UUCP> <4863@alice.UUCP>
Organization: The MITRE Coporation, Bedford, MA
Lines: 36

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