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

Sorry to reply three times - there's a fourth one coming soon, I
think.

Story so far: Just saying that Omega is the probability that a random
program terminates does _not_ show that it's not true that the n-th
bit is 1 iff the n-th TM halts. I showed that this does not
imply that in my first reply.

Now, in my first reply I was under the wrong impression about
how Chaitin _did_ define "random program", so as I pointed
out in second reply the comments I made about what his Omega
can and cannot be aren't right.

But it seems to me that I conceded too much. It seems to me 
today that even knowing that Chaitin's definition 
of "random program" is

"we have a syntax allowing a program to know when it's 
complete. So we define a random program like so: The
interpreter asks for a bit of the program, one bit at 
a time. The system delivers random bits. When the
interpreter sees we have a valid program then that's
our random program - now Omega is the probability that
this random program halts"

is not enough to draw his conclusions. They actually
depend on the specific syntax he's using to decide
when a program is complete and the syntax and semantics
involved in defining whether that program halts. One
can invent a system that constructs random programs
one bit at a time just like Chaitin does, which 
has the property that programs know when they're
complete, and for which defining "random program"
by asking for one random bit at a time leads to
a notion of "random program" precisely equivalent
to what I was using in the first reply (at least
for definable orderings.)

I'm gonna check a few details.


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)