random

[David C. Ullrich]

On Fri, 1 Jun 2001 17:56:26 -0400 (EDT), "Steven D. Majewski"
<sdm7g at Virginia.EDU> wrote:

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

I've read some of his stuff. I didn't see anything there
that gave me any indication to me that JVN was wrong.

When you say something follows from his work it would
be a lot more credible if you could be specific.

>( 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,

Well then I have no idea whatever what you could mean
by saying that he's shown JVN wrong.

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

Maybe yes, maybe no - the word "random" is awfully slippery.

I've seen a lot of misquotation of Chaitin in various
places. "Mathematics is essentially a random process?"
I'd want to see a much more precise statement of that
before deciding that it meant that you could get a
perfect RNG from an arithmetic algorithm.

(We must be talking about "perfectly random", right?
Because if we're talking about "somewhat random"
it's clear we can get that from arithemtic.

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

That's interesting. Seriously. (But it's a comment about
how physics works, I don't see any direct relevance...)

> 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

Yeah. I was hoping you could give a hint _how_ his work
supported what you said, not just a quote of his "opinion"
on the matter.

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

I don't think this is quite accurate. (I _know_ it's at least
a huge oversimplification; for example there's no such
thing as the probability of a program halting until we
specify how the programs are generated.) But even if this
is exactly right I do not see _at_ _all_ how it shows that
JVN was wrong and a perfect arithmetic RNG is possible!

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

This is the sort of statement that leads some mathematicians
to scoff at the guy somewhat.

>|These mathematical truths are beyond the power of mathematical
>| reasoning because they are accidental and random. 

If he has proofs then they're not beyond mathematical reasoning.
If he has no proofs then they're not "discoveries", they're at
best _conjectures_.

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

Saying that the results escape the power of mathematical reasoning
is just silly. If Mathematica derived the results correctly then
the results are not beyond the power of mathematical reasoning,
(and if Mathematica is just guessing then they're not "results".)

What can be is that the results are "incompressible", in that there's
no way even in theory to predict in advance what the answer is for
a given N...

>| This work is an extension of famous results of Gdel and Turing using
>| ideas from a new field called algorithmic information theory. 

There's no doubt whatever that Chaitin has done a lot of extremely 
important and fundametally interesting work. I didnt mean to ask
about that, what I was wondering was how his work led to a perfect
arithmetic RNG, as you seemed to be claiming (and regarding which
I haven't seen anything yet that seems like an explanation.)

There's no doubt that he's done a great deal of fabulous and
important stuff. But it seems clear to a lot of people that 
informal statements about what he's done are very often
simplified beyond the point where they really make sense.
It's like with Godel's incompleteness Theorem(s), as long
as he mentions the subject: Extremely basic and important.
And you see people all the time deducing things from the
incompleteness theorem that simply do not follow at all -
reasoning by very weak analogy, thinking it's a mathematical
proof because the weak analogy involves something that's
been proven.

I know in any case that when you see claims about Godel
and Chaitin in places like sci.math what's claimed is
often ridiculous (and often is not something he said).
Hence my skepticism when I see statements about what
does and what does not follow from his work.

(You said you don't see exactly how all this leads to
an RNG, right? Fine then... note that I never claimed
it didn't, just that I can't see how it does.)

>-- Steve Majewski
>
>
>



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)