Por supuesto, no puede obtener una distribución aleatoria uniforme, o cualquier distribución aleatoria, de un proceso determinista como un generador de números pseudoaleatorios (PRNG). Lo mejor que puede hacer es pedir que la salida de su PRNG satisfaga algunas de las mismas propiedades que tendría una secuencia verdaderamente aleatoria.
Entonces, la idea es esta: primero, elija una lista de propiedades compartidas por las variables uniformes de iid. Luego, encuentre un proceso determinista cuya salida también tenga esas propiedades. La cantidad de propiedades que desea conservar depende de lo que intente hacer. Las simulaciones, en las que simplemente necesitas algunos números para decidir qué sucede, tienen requisitos más débiles que la criptografía y el póker en línea, etc., donde puedes tener un “oponente” que está tratando activamente de descifrar el PRNG.
Con suficiente salida de cualquier PRNG, puede romper la aleatoriedad. La máquina que lo ejecuta almacena una cantidad finita de información, por lo que solo puede pasar por muchos estados antes de repetir. (Por supuesto, en la práctica, un enfoque tan simple probablemente tomaría más tiempo que la vida del universo, incluso en una computadora más antigua).
- ¿Por qué se acepta la tesis de Church-Turing? Tengo problemas para concebir un programa para una máquina de Turing que sume dos números arbitrariamente grandes.
- ¿Cuál es el mejor lenguaje de programación para un matemático?
- ¿Cuál es la forma más sencilla de explicar el problema P = NP?
- ¿Cómo funcionan la Ley Idempotente y la Ley de Dominación?
- ¿Por qué las matemáticas son importantes para los informáticos?