Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site alice.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!alice!ark
From: ark@alice.UucP (Andrew Koenig)
Newsgroups: net.math
Subject: Re: Omega
Message-ID: <4863@alice.UUCP>
Date: Thu, 23-Jan-86 12:51:03 EST
Article-I.D.: alice.4863
Posted: Thu Jan 23 12:51:03 1986
Date-Received: Fri, 24-Jan-86 09:00:55 EST
References: <440@faron.UUCP>
Organization: Bell Labs, Murray Hill
Lines: 14

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