random

[David C. Ullrich]

On Sun, 03 Jun 2001 15:21:13 GMT, ullrich at math.okstate.edu (David C.
Ullrich) wrote:

>On Sun, 03 Jun 2001 05:51:12 GMT, "Nick Perkins" <nperkins7 at home.com>
>wrote:
>
>>
[...]
>>I may be mangling this a tiny bit, not being a mathematician, but I can see
>>where some of the confusion may have set in.  It is easy to mis-understand
>>Chaitan's work as giving an algorithm for producing a 'truly' random number.
>>In fact, what I think he shows, is that there is a number that is 'truly
>>random', but producing the Nth bit of that number requires a program that is
>>at least N bits long.
>
>Read it again. There is _no_ algorithm to find the N-th bit. None 
>whatever.
>
>That's not quite accurate, or at least it's susceptible to 
>misinterpretation. Technically, the bits are recursively enumerable
>but not recursive: There _is_ an algoorithm which will ouput
>a sequence of reals, and those reals _will_ converge to Omega.
>Hence (well, there are details here as well, but let's just say
>"hence") the bits in the approximations _do_ converge to the bits
>in Omaga. So there _is_ something which will eventually print
>out the first 100 bits of Omega. But there is no way to know
>_when_ it's got the first 100 bits right.
>
>Um, that's the way it seems to me, anyway, based on what I thought
>that stuff was all about and what I read just now in that paper.
>I could be misinterpteting something.

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

(No correction to my explanation of what I meant, just on
the usage of the big words.)


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)