random

[David C. Ullrich]

On Sun, 3 Jun 2001 18:14:47 -0400, "Tim Peters" <tim.one at home.com>
wrote:

>[David C. Ullrich]
>> ...
>> Not that readers are likely to be reading carefully enough that it's
>> going to matter, but just for the sake of telling no lies: I put
>> my finger on what was bothering me about what I said here.
>> It's not true that the sequence of bits of Omega is recursively
>> enumerable. What's true (assuming that the N-th bit is 1 if the
>> N-th program halts and 0 otherwise) is that the sequence of N
>> for which the N-th bit is 1 is recursively enumerable. The
>> set of N for which the N-th bit is 0 is _not_ recursively
>> enumerable (and hence the sequence of bits of Omega is not
>> recursively enumerable.)
>
>It's the "assuming that the N-th bit is 1 [iff] the N-th program halts"
>that's off.  Omega is the probability that "a random" program halts, and it
>won't take long to figure out that "N'th-bit = halts(N-th program)" doesn't
>work for that

Drat. I looked, and of course I did in fact have the definition 
bollixed - the method he uses to "generate a program by coin-tossing"
is not what I recalled. We _do_ need a definition of "random
program", and he does give one, but it's not what I thought it
was.

So much of what I said just now about Omega is not correct.
But otoh it's because I mis-recalled the definition of
"generate a program by coin tossing". It is _not_ true that
it doesn't take long to figure out that "n-th bit = 1 iff
n-th TM halts" cannot give the probability that a random
TM halts - the following parenthetical comment cannot
show that Omega could not be what I thought, because
you don't use anything about the particular distribution
Chaitin uses, and with _some_ distributions Omega
_would_ be as I said.

Or to put it another way:

> (e.g., if the 0'th program happens to halt, that would imply
>the halting probability is >= 1/2 across all programs -- but the 0'th
>program isn't generally that smart <wink>). 

Nope - this sounds good but it's specious. With the distribution
I thought Chaitin was using it _would_ follow that Omega > 1/2
if the 0-th program happened to halt, and with the distribution
he _does_ use things that are equally winkie-sounding _do_
follow: Pick a program that does happen to halt. If that program
is K bits long then the fact that that particular program halts
_does_ show that Omega > 2^{-K}. That program happens to
be smart enough to imply that the halting probability is
larger than something - with a different distribution it would
just imply that the halting probability is larger than a different
thing.

So I lied, but it's not as obvious as you say that my lie
_must_ have been wrong - as long as we're just talking
about "a random program" without specifying the
distribution what I said could have been right regardless
of questions of how smart the first program is.

I guess I was misled by his display

<style TYPE="text/css">
<!--
EM {font-family: Symbol; font-style: normal}
-->
</style>

<P><CENTER>
<EM>W = å</EM> <SUB>p halts</SUB> 2 <SUP><EM>-</EM>|p|</SUP>
</CENTER></P>

which certainly looks like the binary expansion of a number if you 
don't look closely - each program that halts adds a power of
2 to the probability, just like in

<P><CENTER>
<EM>W = å</EM> <SUB>p<SUB>j</SUB> halts</SUB> 2
<SUP><EM>-</EM>j</SUP>
</CENTER></P>

That's the best excuse I can contrive. Oh well. 
Thought I had the problem of inexact floating point solved.

David C. Ullrich
***********************
"Sometimes you can have access violations all the
time and the program still works." (Michael Caracena,
comp.lang.pascal.delphi.misc 5/1/01)