Re: Penrose (Was: Infinities)

Wayne Hayes (wayne@cs.toronto.edu)
Mon, 10 Nov 1997 11:33:05 -0500


Hal Finney <hal@rain.org> writes:
>There are pseudo random number generators which are believed to be
>indistinguishable from true random number generators even with all the
>computing power in the entire universe (by some definition).

Do you have a reference for this? The best ones that I've heard of
that are purely algorithmic are the well-known linear congruential
ones. They are hard to distinguish from truly random ones, but
definitely not if you have "all the computing power in the universe".
This is because if the random generator has N bits, then it will
*always* show correllations in an N-dimensional correllation plot.
Mind you, to get good correllations requires filling up the
N-dimensional space to some degree, which can take time exponential in
N, so perhaps it's just an LC algorithm with large N.

Anyway, a reference would be nice, if only because I'm really
interested in these generators, if they exist.