random

[Nick Perkins]

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

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.

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