David C. Ullrich
ullrich at math.okstate.edu
Tue Jun 5 16:41:47 CEST 2001
On Sun, 3 Jun 2001 18:14:47 -0400, "Tim Peters" <tim.one at home.com>
>[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
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,
More information about the Python-list