random

[Steven D. Majewski]

On Fri, 1 Jun 2001, David C. Ullrich wrote:

> On Thu, 31 May 2001 19:52:28 -0400 (EDT), "Steven D. Majewski"
> <sdm7g at Virginia.EDU> wrote:
> >
> >On 31 May 2001, Mark 'Kamikaze' Hughes wrote:
> >
> >>   "Anyone who considers arithmetical methods of producing random numbers
> >> is, of course, in a state of sin." -John Von Neumann
> >> 
> >>   Unless you have random-number-generating hardware, you don't really
> >> have truly random numbers.
> >
> >That's what I was always taught, however in the light of 
> >Gregory Chaitin's work or randomness in arithmetic: 
> >
> >	<http://www.cs.auckland.ac.nz/CDMTCS/chaitin/>
> >
> >JVN may have been wrong. 
> 
> ??? There's a _lot_ of stuff there. 
> 
> Could you give us a hint regarding exactly what work
> of Chaitin's shows we can get "truly random" numbers from
> arithmetic algorithms?

Pick any one at random, David! 
( Starting from the top down isn't a bad strategy either. ) 

I'm not sure that there is a practical method for a RNG there,
and I certainly don't grasp it all, but Chaitin asserts that 
mathematics is essentially a random process.  And you ought
to be able to get random numbers out of a random process -- 
right ?  Some of the interest from Physicists in Chaitin's work
is that if mathematics is a random process, then that may be
at the root of quantum randomness. *IF* you can believe his
assertion, then that source of randomness is easier to swallow
than the idea that the act of abservation causes some magical 
effects. 

 The arguments that go with that assertion are more than I 
could summarize here, even if I did grasp it all myself. 

>From the Nature article "Randomness everywhere" 
<http://www.cs.auckland.ac.nz/CDMTCS/chaitin/nature.html>:

| This recent work reinforces the message of algorithmic information
| theory that randomness is as fundamental and as pervasive in pure
| mathematics as it is in theoretical physics. In our opinion it also
| gives further support to `experimental mathematics', and to the
| `quasi-empirical' view of mathematics which says that although
| mathematics and physics are different, it is more a matter of degree
| than black and white


> A physical RNG can have the property that one cannot make 
> any prediction about the value of the next bit even given
> _complete_ information about how the numbers are being
> generated. An arithmetic algorithm with this property seems
> obviously impossible - if you know the algorithm and you
> know the current state of the RNG you can predict the
> next number... whatever the algorithm is, someone with all
> this information can devise a "randomness test" that the
> RNG will fail miserably. Or so it seems.

Chaitin's Omega number is basically the probability that a 
randomly generated program will halt -- which is undecideable,
but can be approximated experimentally and observing it -- 
each binary digit of that probability is random. 

But, how this ties into a basic randomness at the root of
mathematics is more than I can grok yet, but some of it is
in  "Randomness and Complexity in Pure Mathematics"
<http://www.cs.auckland.ac.nz/CDMTCS/chaitin/ijbc.html>:

| One normally thinks that everything that is true is true for a
| reason. I've found mathematical truths that are true for no reason at
| all. These mathematical truths are beyond the power of mathematical
| reasoning because they are accidental and random. 
|
| Using software written in Mathematica that runs on an IBM RS/6000
| workstation, I constructed a perverse 200-page algebraic equation with a
| parameter N and 17,000 unknowns: 
|
| Left-Hand-Side(N) = Right-Hand-Side(N). 
| For each whole-number value of the parameter N, ask whether this
| equation has a finite or an infinite number of whole number
| solutions. The answers escape the power of mathematical reason because
| they are completely random and accidental. 
|
| This work is an extension of famous results of Gdel and Turing using
| ideas from a new field called algorithmic information theory. 


-- Steve Majewski