random

[David C. Ullrich]

On Sun, 03 Jun 2001 05:51:12 GMT, "Nick Perkins" <nperkins7 at home.com>
wrote:

>
>"Tim Peters" <tim.one at home.com> wrote in message
>> Chaitan is a bit of a self-promoter, and his rhetoric is often colorful,
>but
>> by all indications his work is rock solid.   A very nice high-level intro
>is
>> this transcript of a lecture he gave at CMU:
>>
>>     http://www.cs.umaine.edu/~chaitin/cmu.html
>>
>>
>
>I just read (almost all of) that page.
>Very mind-blowing stuff.
>
>I am not sure, but think I managed to find the answer to this question:
>
>>"David C. Ullrich" <ullrich at math.okstate.edu> wrote in message
>>news:3b17a2f1.411766 at nntp.sprynet.com...
>>    ...
>>> Could you give us a hint regarding exactly what work
>>> of Chaitin's shows we can get "truly random" numbers from
>>> arithmetic algorithms?
>
>Chaitan's work seems to imply that no algorithm (of finite size) can
>possibly produce 'perfectly random' numbers.

Before we can prove this we need a definition. Given a perfectly 
reasonable definition (cf post which may appear sometime when the
news server at the office wakes up) it does not require Chaitin's
work to show this, it's trivial.

>Chaitan says "..something is random if the smallest program that calculates
>it is the same size as it is..".  He defines the randomness of data as the
>inverse of it's 'structure', where structure is defined as the length of the
>smallest program that produces the data.  So it would seem to me that any
>algorithm (or program) can not produce can not produce numbers of 'infinite
>randomness'.
>
>The very idea of 'infinite randomness', in all it's unattainable glory, is
>somehow very pure and clear in everyone's mind.  It is, after all, the first
>concept of randomness that we all learned as children: that something is
>simply unpredictable, period.  Strange that it takes centuries of advanced
>math to try to pin down exactly what randomness means.
>
>Chaitan gives an example of a 'truly' random number, based on the 'Halting
>Problem'.  He shows that the probablity of a program halting is
>fundamentally unknowable.  It is an actual number between zero and one, but
>where it is in that range is not only unknown, but 'unknowable'.  In binary
>representation, we can not even get the slightest idea of what the first
>digit is, no matter how long of a program we write to figure it out.
>
>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.

>...anyway, my brain is going all loopy at this point, and I may have
>min-understood Chaitan, but I think I understood that Chaitan's ideas
>support (or conclude, or rely on) the idea that no finite algorithm can
>produce 'truly random' numbers.
>
>Have I mis-understood anything?
>
>Did anyone else read that page?  What did you think?
>
>No? ..here it is again: (thanks, Tim)
>>     http://www.cs.umaine.edu/~chaitin/cmu.html
>
>
>
>



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)