All pseudorandom generators are theoretically periodic?

48 Views Asked by At

Is there a pseudo-random generator with an infinite period?

2

There are 2 best solutions below

1
On

No.

Any pseudo-random generator relies on a finite amount of memory, say $b$ bits, and cannot be in more than $2^b$ different states. $2^b$ is an absolute limit on the period. (Though it can easily be made to exceed the number of electrons in the Universe.)

0
On

In theory, one could conceive of an algoritm that periodically allocates more memory as it needs it. So there could be an algorithm without period. But it could never be implemented correctly in this universe as we know it, and presumably, not much research has gone into constructing such algorithms.

Any algorithm you would actually use in practice is meant to be implemented correctly on a computer. And since any computer has a limited amount of memory, the algorithm won't be able to increase its memory usage indefinitely. This necessarily induces periods, as the computer at some point must reach a state it has already been in, and from that point on everything will repeat.