¿Por qué es difícil para una computadora obtener un número aleatorio?

Esta es una gran pregunta en realidad. Porque profundiza en cuestiones relacionadas con la inteligencia artificial y las computadoras serán creativas o tendrán emociones.

Comencemos mirando lo que hace una computadora de manera simplificada.

  1. Todo en una computadora es un número, ¡todo! Desde imágenes hasta video, sonido y letras. Esto se debe a que todo está “codificado”. Toma las cartas que estás leyendo. Existe un estándar llamado Código Estándar Americano para el Intercambio de Información (ASCII). Es una tabla que determina cómo codificar las letras. Dice que una ‘A’ mayúscula es 65 y que ‘B’ mayúscula es 66. Una pequeña ‘a’ es 97 y una pequeña ‘b’ es 98. De esta manera, un archivo que debe contener texto puede ser transferido por uno computadora a otra y aún ser utilizable. Es una forma acordada de representar letras como números.
  2. En el corazón de una computadora hay una CPU (unidad central de procesamiento) que realiza operaciones simples, como copiar un valor de un lugar en la memoria a otro, o sumar dos números y almacenarlos en algún lugar de la memoria. También contiene instrucciones para la comparación, como comparar el número en la ubicación de memoria 1.456 con el número en la ubicación 5.432 y luego cambiar qué código ejecutar (ramificación) en función de los resultados.
  3. Los programas mismos consisten en estas instrucciones de CPU y, como todo lo demás, están codificadas como números. La operación 65 podría ser “agregar el valor de dos registros juntos para almacenar en el primer registro” y el siguiente byte es el primer registro con el siguiente byte como el siguiente registro. Entonces, la serie de números en la memoria 65 12 5 significa sumar el valor del registro 12 al registro 5 poniendo los resultados en el registro 12.

Es posible que haya notado que 65 es una ‘A’ mayúscula en ASCII, pero en nuestra pseudo CPU significa agregar dos registros juntos. Esto está bien, son dos codificaciones diferentes para dos tipos diferentes de datos (texto y programas). Pero espera, ¿estoy diciendo que un programa son datos? Sí, para la CPU, un programa es simplemente una serie de números que indican paso a paso qué hacer. Y dada la misma entrada, SIEMPRE realizará esos pasos exactamente de la misma manera. EXACTAMENTE sin desviación, siempre que la entrada sea la misma.

Aquí hay un ejemplo de un programa simple:

1) Cargue el valor de la ubicación de memoria 10 en el registro 1
2) Reste el valor en la ubicación de memoria 11 del registro 1 y almacene en el registro 1
3) si el valor en el registro 1 es menor que 10, salte al paso 6
4) imprimir “10 o más”
5) bifurca al paso 7
6) imprimir “Menos de 10”
7) detener programa

Entonces, los programas toman el valor de la memoria (datos iniciales) y lo cargan en una ubicación especial llamada registro que está en la CPU. Luego resta el valor de la ubicación 11 (también los datos iniciales) y los almacena en el registro 1. Si el valor en el registro 1 es menor que 10, imprime “Menos de 10” y termina, de lo contrario, imprime “10 o mayor” y finaliza. Si los valores iniciales en las direcciones 10 y 11 nunca cambian, el programa nunca puede tomar otra ruta. Si los datos iniciales cambian, puede obtener una salida diferente.

Cómo se aplica esto a los números aleatorios

Ahora tiene un programa que desea generar números aleatorios, el problema es que siempre toma los mismos pasos y los datos iniciales SIEMPRE generarán la misma salida. Esa es la dificultad aquí. ¿Cómo se hace un número aleatorio a partir de un algoritmo que siempre sigue los mismos pasos cuando se le da la misma entrada? Sin hardware especializado, no puedes. Lo que obtienes es que, dado un estado inicial (entrada inicial), puede generar una serie de números, comenzando con ese estado inicial, que se producen de una manera que la salida parece aleatoria en un rango determinado. El número inicial se llama semilla. Dada la misma semilla (estado inicial), se producirá la misma cadena de números aleatorios al cambiar los bits. No son realmente al azar, simplemente están tan mezclados en su progresión que parecen aleatorios. Se llaman “pseudoaleatorios” porque si conoce ese estado inicial y cuántas veces ha pasado por el algoritmo, puede conocer el siguiente número.

En la imagen de arriba, se dibujaron 100,000 píxeles usando un generador de números pseudoaleatorios (PRNG) para generar las coordenadas de los puntos (dado que en números verdaderamente aleatorios se pueden elegir los mismos números más de una vez, es probable que no haya 100,000 puntos ) Si ejecuta el programa nuevamente sin cambiar nada, obtendrá exactamente la misma imagen. Si cambia la semilla de 1 a otra cosa, incluso 2, la imagen se vería muy diferente. Al elegir una nueva semilla, saltas a la serie de números en una nueva ubicación que parece darte números aleatorios, pero en realidad es la misma lista de números, pero comienza en otro lugar de la lista.

Entropía

La mayoría de los PRNG buenos usan un método cíclico para generar números, lo que significa que toma el valor del último, ejecuta el algoritmo y el estado ahora es diferente para generar el siguiente. Digamos que nuestro PRNG comienza en 10, luego genera 15, luego genera 7 y luego 8,000.

Ahora supongamos que entre el 10 y el 15 cambiamos el estado interno del PRNG. Ahora generaría algo diferente, podría ser 10, 105, 423, 87. Esto se llama entropía. Si cambiamos el estado, cambiamos los valores, pero el problema es que si el cambio del estado forma parte del algoritmo, generamos los mismos números. Si podemos encontrar una fuente que esté fuera del algoritmo que no sea un algoritmo en sí mismo, podemos producir mejores números aleatorios.

Las fuentes de entropía a menudo provienen de eventos físicos. Tal vez los milisegundos entre interrupciones del teclado, el tiempo de tus dedos mientras escribes. Esa es una fuente cambiante porque incluso si escribe lo mismo una y otra vez, es tan impreciso a una escala de milisegundos que serán aleatorios, al menos caóticos. Tal vez son los tiempos de la interfaz de disco para discos de metal giratorio de la vieja usanza. Dependiendo de dónde estén los sectores en el disco debajo de las cabezas, incluso leer el mismo sector una y otra vez produce diferentes tiempos. Esa es una fuente física de entropía. El movimiento del mouse es otro.

Realmente se reduce a un concepto básico:

entrada de datos = salida de datos.

Misma entrada de datos = misma salida de datos.

Muchas personas creen que una IA necesitaría un componente aleatorio para ser creativo, pero en realidad ese no es el caso. Las partículas del universo, aunque son inimaginablemente complejas en interacción, operan por leyes del universo que no cambian. Su cerebro opera con estas partículas, que dado el mismo estado (complicado o no) de interacción produciría los mismos resultados. Entonces, tal vez realmente no exista nada aleatorio si supieras 1) todas las reglas de la interacción partícula / onda del universo, 2) el estado inicial y 2) dónde están todas esas partículas en este momento.

(Es binario: o lo entiendes o no).

Aunque es un número extremadamente grande, una computadora solo puede estar en un número finito de estados. (Condiciones, colección de configuraciones de memoria). Una computadora necesariamente progresará de un estado a otro de una manera predeterminada. Si bien la secuencia puede ser grande, no es aleatoria. La mayoría de los generadores de números aleatorios operan con un rango de estados mucho más pequeño. En ese caso, la base de la secuencia de números aleatorios que produce puede deducirse mediante la detección de patrones en una secuencia de salidas. Si bien es casi aleatorio, no es estrictamente hablando aleatorio.

Una semilla proporciona un nuevo modificador para el estado en el que se encuentra un generador de números aleatorios. La selección prudente de una nueva semilla en cada uso del generador de números aleatorios asegurará que, para la mayoría de los propósitos prácticos, la salida pueda considerarse aleatoria. Para mayor seguridad, las técnicas criptográficas: el cifrado de la salida de un RNG podría incluso ir más allá de los criterios NIST de aleatoriedad.

Recomendación para la generación de números aleatorios utilizando generadores deterministas de bits aleatorios

Esta Recomendación especifica técnicas para la generación de bits aleatorios que luego pueden usarse directamente o convertirse a números aleatorios cuando las aplicaciones que usan criptografía requieren valores aleatorios. Hay dos estrategias fundamentalmente diferentes para generar bits aleatorios. Una estrategia es producir bits de forma no determinista, donde cada bit de salida se basa en un proceso físico que es impredecible; Esta clase de generadores de bits aleatorios (RBG) se conoce comúnmente como generadores de bits aleatorios no deterministas (NRBG) 1. La otra estrategia es calcular bits de manera determinista usando un algoritmo; esta clase de RBG se conoce como generadores deterministas de bits aleatorios (DRBG)

Es fácil de responder, porque la computadora no puede hacer nada “al azar”. En general, la CPU está calculando instrucciones fáciles, como “sumar 2 números A y B y poner el resultado en C; si C> 0, vaya a la dirección 0xFFFAAA; … “. No hay instrucciones de CPU como “tomar algo al azar”: la CPU en sí es algo bastante fácil que solo puede realizar operaciones fáciles como “sumar”, “restar”, “cambiar”, etc.

Entonces hay 2 formas:

  • use una fórmula matemática para generar valores pseudoaleatorios; puede parecer aleatorio, pero en realidad es solo una fórmula.
  • use una fuente aleatoria externa implementada por hardware, como ruido de transistor amplificado o algo así.

Es fácil generar un número “aleatorio”, pero generar números que estadísticamente realmente son aleatorios es un problema difícil, porque “fórmula” y “aleatoriedad” son, por definición, dos cosas opuestas.

Ya hay respuestas decentes, pero me gustaría mantenerlo un poco más simple.

Es porque las computadoras son máquinas deterministas . Eso significa que siempre que se inicialicen de la misma manera, se comportarán exactamente de la misma manera. Si la salida fue 42 la primera vez, siempre será 42. Y, por lo tanto, nunca pueden producir un número aleatorio.

Las computadoras son deterministas por diseño: es perfectamente posible hacer máquinas que tengan un comportamiento impredecible. (Solo equípalos con un pequeño robot que lanza una moneda y una cámara para grabar el resultado, ¡jaja!) Pero hasta hace poco, la gente simplemente nunca encontraba eso lo suficientemente importante como para molestarse.

Cuando las personas necesitaban números aleatorios, el problema se solucionó mediante el uso de una combinación de datos ruidosos del hardware (reloj, movimientos del mouse, etc.) y generación de números pseudoaleatorios (que realmente debería llamarse “aleatoriedad falsa”, pero funciona bien en práctica).

Sin embargo, desde hace poco, Intel ha estado equipando sus procesadores con un generador de números aleatorios. Así que ahora, uno puede tener números aleatorios verdaderos con bastante facilidad.

Aquí hay muchas buenas respuestas con muchos detalles. Pero sentí que una respuesta simple podría ser suficiente.

Usando una fórmula, una computadora puede generar un número pseudoaleatorio que sea lo suficientemente bueno para la mayoría de los propósitos (si es necesario, hay hardware disponible para números aleatorios verdaderos).

Como los PRNG necesitan una semilla inicial, un programador podría usar el tiempo actual en segundos o algún otro evento.

Por lo tanto, sugeriría que las computadoras son capaces de números aleatorios, con bastante facilidad, siempre y cuando comprendamos que, si bien parecen ser aleatorias, es teóricamente posible predecirlas (pero, hasta donde sé, no es posible).

Además, Linux proporciona números aleatorios en un “grupo de entropía” generado a partir de eventos (consulte el artículo / dev / random en wikipedia).

No es difícil en absoluto una aleatoriedad suficiente para satisfacer el 99.99% de los casos.

C ++: rand ();

Python: random.randint (a, b)

(para obtener una secuencia diferente en cada ejecución, puede inicializar con la hora del sistema: srand (time (null))).

Si quieres VERDADERAMENTE números aleatorios, entonces estás preguntando mucho, no es que las computadoras puedan hacer álgebra realmente correcta en los reales, o dibujar círculos verdaderamente circulares, o incluso cuadrados realmente cuadrados.

Es cuestionable si algo es verdaderamente aleatorio, algunos han discutido el uso de la descomposición de partículas o los efectos cuánticos, pero nadie está seguro de que realmente obtengamos un verdadero número aleatorio, o incluso de que tal concepto sea posible. Ignorando la compleja cuestión de la teoría cuántica, un valor verdaderamente aleatorio por definición no debería depender del universo pasado, por lo que es acausal.

En palabras simples, la computadora funciona en base a algoritmos (cierta lógica o patrones), por lo que no puede generar números aleatorios reales. El cerebro humano es superior a las computadoras en este caso. Por ejemplo, puede pensar en elegir 10 números de 1 a 100 números sin ninguna lógica o patrón, como 22, 67, 29, 84 … y así sucesivamente. Aquí has ​​generado números realmente aleatorios.

Entonces, ¿qué computadora tiene mucha potencia de procesamiento, tenemos una mente hermosa!

Citado de “Las computadoras son pésimos generadores de números aleatorios”:

Los números pseudoaleatorios se eligen con igual probabilidad de un conjunto finito de números. Los números elegidos no son completamente aleatorios porque se utiliza un algoritmo matemático definido para seleccionarlos, pero son lo suficientemente aleatorios para fines prácticos .

Usan un LFSR, pero lo que escupen es siempre el mismo orden de números “aleatorios” si siempre comienza (semilla) con el mismo número.

Un humano presionando una tecla (tiempo) podría crear una semilla aleatoria.
El ruido de radio o un PLL que aún no se resolvió también es bastante bueno.