¿Todas las funciones generadoras de números (pseudo) aleatorios son cíclicas?

Answer 1

Todos los generadores de números pseduo-aleatorios solo de software son cíclicos, pero el ciclo puede ser lo suficientemente largo como para ser suficiente para fines prácticos.

Un PRNG es una máquina de estado finito. Tiene cierto número de bits de estado interno, no tiene entradas que brinden nueva información y funciona de manera determinista. Debido a que solo hay N bits de estado, solo puede haber [math] 2 ^ {N} [/ math] diferentes estados internos. Después de que se hayan generado tantos números, se debe haber alcanzado el mismo estado al menos dos veces, y posiblemente más. Debido a que el PRNG es determinista, una vez que ha alcanzado un estado anterior producirá la misma salida, causando un ciclo.

Sin embargo, el generador de números aleatorios puede aumentar su estado interno al mezclar fuentes externas de aleatoriedad, como la información de temporización de los dispositivos de E / S. Si esto se hace de manera continua, entonces la salida no necesita ser cíclica.

Answer 2

Algunos pueden ciclar por razones triviales. Pero la respuesta a si todos los ciclos de PRNG es “sí, pero solo por razones triviales”, es decir, si se quedan sin recursos. Por definición, un programa informático completo de Turing es capaz de calcular sin terminación, y no terminar necesariamente significa entrar en un ciclo (por ejemplo, ‘calcular los dígitos de la constante matemática pi’). Como ejemplo de tal función o autómata, tome el llamado Autómata Celular Elemental 110, no tiene ciclos para algunos cálculos (como se ha demostrado que es universal de Turing), solo tendría un ‘ciclo’ si se queda sin memoria y se reinicia.