random

[Alex Martelli]

"David C. Ullrich" <ullrich at math.okstate.edu> wrote in message
news:3b17ed86.19508127 at nntp.sprynet.com...
    ...
> >> 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
> >
> >"From impossibilia sequitur quodlibet".  *IF* you could
> >have complete information, *THEN* you could predict all
> >you want.  Problem is, you CANNOT have complete info due
> >to that Heisenberg fellow, therefore you cannot predict
> >(precisely).
>
> Huh? You cannot have complete information about a
> _physical_ RNG, which is why you _can_ get "really
> random" numbers from a physical RNG. But you certainly

The quote above contains the premise "even given _complete_
information".  Now you say "you cannot have complete
information".  Well, if this latter statement is true, then
the premise is always false, and from a false premise
any conclusion follows, as Pseudo-Scotus proved and I
recalled in his very words -- except I used 'from' instead
of 'ab' as a hint.

So, to recap: the post I was replying to states that given
[what you now state is] an impossibility, yet a conclusion
[predicibility of next bit] does NOT follow.  Pseudo-Scotus
says that given an impossibility ANYTHING follows (you
can prove any theorem and its contrary if your set of
axioms include a contradiction).


> can have complete information regarding the state
> of an _arithmetic_ _algorithm_.

I assume that is your definition of "an algorithm"?  That
its state be finite?  While you are absolutely certain that
NO physical system can be described in finite terms,
EVER?  Wow, last time I met anybody so sure of things,
it was a priest:-).

> > From what I know of Chaitin's life work,
> >it started with just the idea of defining randomness in
> >terms of minimal amount of information (in bits) you need
> >for prediction.  If YOUR definition of 'randomness' is
> >something that needs INFINITE number of bits to predict,
> >go ahead and have fun, but you're unlikely to get some
> >constructive results out of it.
>
> It seems fairly likely that there's a point here, but
> I don't see what it is. Given an arithmetic algorithm
> it does _not_ take an infinite number of bits to do
> any predicting.

Agreed (given a definition of algorithm that requires it
to be finite, this is a tautology).  So, the amount of
randomness (which is a finite amount of randomness)
is described as the number of bits (a finite one) needed
for said prediction.  (Over-simplifying a bit here:-).

If you think interesting and fruitful mathematical theories
can be constructed around measures of randomness which
only consider infinities, go right ahead and don't let the
mathematicians scoffing at you put you off -- if Feynman
could simplify away infinities and come up with stuff,
why not you, after all?

Meanwhile, some of us working with finite machines,
communication channels of finite capacity, and so on,
are very interested in the currently accepted, operational
definitions of randomness in finite terms given by Chaitin,
Solovay, and so on.  It's about mathematics rather than
physics, and rather 'solid' maths in a sense -- it seems
Chaitin's books are chock full of working Lisp code that
exemplifies what he's saying.


> >A physical system that is macroscopic enough to escape
> >Heisenbergian conumdrums
>
> There is no such system.

In this case, no physical computer is predictable, and all
we study about algorithms are abstractions -- since a
computer system IS a physical system, then ALL bits
coming out from it must be random in your sense of
the word.  Defining things in terms of infinities, absolutes
and utter unshakable certainties does tend to have this
risk -- discussion is trivialized rather than concrete and
fruitful.  But, hey, if that's what floats your boat...

If, on the other hand, you maintain that the output
from a physical system CAN be predictable if that
system is a computer running your program, then
what makes you SO certain that NO other physical
systems can also be predictable in the same sense?-)


> > could also be describable in
> >a finite number of bits, in terms of enabling somebody
> >to predict the 'next outcome'.  That was, if I'm not
> >mistaken, Laplace's take on probability (and not his
> >only), all the way up to Einstein's in this century --
> >that it's all about hidden variables, information that
> >we do not happen to have, rather than information that
> >intrinsically CANNOT be had.
>
> I continue to miss your point. See, Einstein was
> wrong about quantum mechanics (or so the people best
> qualified to know believe). I forget whose theorem
> it is (Von Neumann's, I think maybe!) that you
> _cannot_ describe "classical quantum mechanics" in
> terms of hidden variables.

A couple centuries ago all scientists were certain of
one thing, now they're all becoming certain of another,
and I won't be around in a couple more centuries to
laugh at the likely-different certainties they'll have
then.  Meanwhile, mathematics is far from exempt
from paradigm shifts, of course, but those never do
'contradict' the previous certainties (META-maths is
different that way of course -- cfr. Russel's well
known demolition of Frege's lifework:-), rather
extend and generalize on them.

I'm currently more interested in what a mathematician
like Chaitin has to say about randomness, particularly
of the finite kind which I can handle in a computer (if
and only if it's a physically predictable system:-) than
in what physicists or other philosophers have to say
about randomness, particularly if that requires dabbling
with infinities.  Being an engineer myself, I do place a
prize on USEFUL theories, after all.


> >Measuring randomness in terms of amount of information
> >seems like it works nicely.
>
> I'm certain it does. I don't see how saying that
> says anything about VN being wrong with his comment
> about how arithmetic RNG's cannot be perfect.

If by "perfect" randomness VN meant an infinite amount
thereof (by Chaitin measure), he might have said that
(were it not for the little detail that Chaitin was probably
not even in primary school back then, I guess).  The
quote talks generically about "random", without using
the word "perfect" you now insert, and without any
specification of infiniteness as a prerequisite, and, as
such and without the needed qualifications, it is not
correct.  _with_ the qualifications you want to place,
it seems to become tautological ("I define X as being
something that requires infinities: no finite system can
reach X, it can only approach it") and therefore sterile
and uninteresting, unless there are hidden layers of
exoteric meaning nesting in it, I guess.


Alex