Get best of the week

Generando números pseudoaleatorios usando un autómata celular: Regla 30

Los generadores de números pseudoaleatorios dan números de manera determinista, pero generalmente estos números parecen no periódicos (aleatorios). Al menos en la mayoría de los casos, el uso de tales números generalmente ocurre. El generador toma un valor inicial (idealmente un número aleatorio verdadero) y genera una secuencia de números, que funciona en función del valor inicial y / o el número anterior en la secuencia. Dichos números son pseudoaleatorios (y no números aleatorios verdaderos) debido al hecho de que si se conoce el valor inicial transmitido al generador, estos números pueden generarse nuevamente algorítmicamente. Se generan números aleatorios verdaderos utilizando hardware especial o ciertos fenómenos físicos: fluctuaciones de pulso en el volumen sanguíneo, presión atmosférica, ruido térmico, procesos cuánticos, etc.



Hay muchas formas de generar números pseudoaleatorios. Por ejemplo, el algoritmo Blum - Blum - Shub , el método del cuadrado medio , el método de Fibonacci con retrasos . Hoy hablaremos sobre la generación de números aleatorios utilizando la Regla 30 , que utiliza un enfoque ambiguo que implica el uso de un modelo de autómata celular . Este método pasó muchas pruebas de números aleatorios estándar y se utilizó en Mathematica para generar enteros aleatorios.

Autómata celular


Antes de llegar al tema de la Regla 30, tomemos un tiempo en autómatas celulares. Un autómata celular es un modelo discreto que consiste en una cuadrícula regular de celdas de cualquier dimensión. Cada una de las celdas reticulares puede estar en uno de un conjunto finito de estados. Además, para cada celda, se define un concepto como "vecindario". En las proximidades de una determinada celda, por ejemplo, todas las celdas ubicadas a una distancia de no más de 2 pueden entrar. Hay reglas que determinan cómo las células interactúan entre sí y pasan a la siguiente generación (estado). Estas reglas están representadas principalmente por funciones matemáticas (programables), que dependen del estado actual de las celdas y del estado de sus vecinos.


Descripción del autómata celular La

descripción del autómata celular de la figura anterior le permite descubrir que cada celda puede estar en uno de los dos estados finales:0(se muestra en rojo) y1(se muestra en negro). Cada celda pasa a la siguiente generación, asumiendo un nuevo estado resultante de aplicar la operaciónXORa sus 8 vecinos. La primera generación (estado inicial) de la red se establece aleatoriamente. El funcionamiento de este autómata celular se muestra a continuación.


El

autómata celular basado en XOR en acción La idea de un autómata celular surgió en la década de 1940 gracias a Stanislav Ulam y John von Neumann . Los autómatas celulares han encontrado aplicación en informática, matemáticas, física, en la teoría de sistemas complejos, en biología teórica y en problemas de modelado de la microestructura de medios y materiales. En la década de 1980, Stephen Wolfram realizó un estudio sistemático de un autómata celular unidimensional (también llamado autómata celular elemental), en el que se basa la Regla 30.

Regla 30


La regla 30 es un autómata celular elemental (unidimensional) en el que cada célula puede residir en uno de los dos estados finales: 0(glóbulos rojos en la figura siguiente) y 1(células negras). La vecindad de la celda está representada por sus dos vecinos más cercanos ubicados a la izquierda y derecha de la misma. El siguiente estado (generación) de una celda depende de su estado actual y del estado de sus vecinos. Las reglas para la transición de celdas al siguiente estado se muestran en la siguiente figura.


Regla 30

Estas reglas de transición a un nuevo estado de celdas pueden simplificarse escritas comoleft XOR (central OR right).

Producimos las celdas del autómata en forma de red bidimensional, cada fila de las cuales representa una generación (estado). Cuando se calcula la próxima generación (estado) de celdas, se muestra debajo del último estado conocido. Cada fila contiene un número finito de celdas que, al final, "se repiten".


Regla 30 en acción

El patrón anterior surge del estado inicial (línea 0) cuando una celda tiene un estado1(negro) y todas las celdas que lo rodean tienen un estado0(rojo). El estado de las celdas en la próxima generación (línea 1) se calcula de acuerdo con la regla anterior. La cuadrícula vertical representa el tiempo, y las intersecciones de filas y columnas representan el estado de una celda particular en una etapa particular del desarrollo del sistema.


Generación ty generación t + 1

A medida que se desarrolla el patrón, a menudo aparecen triángulos rojos de diferentes tamaños, pero, en general, no se puede reconocer un patrón distinguible en la estructura resultante. El fragmento anterior de la red se realiza en un momento elegido arbitrariamente en el tiempo. Aquí puedes ver el caos y la aperiodicidad. Esta propiedad es la Regla 30 y se usa para generar números pseudoaleatorios.

Generación de números seudoaleatorios


Como ya se mencionó, la Regla 30 demuestra un comportamiento aperiódico y caótico. Como resultado, su aplicación conduce a la creación de patrones complejos y, al parecer, aleatorios de acuerdo con reglas simples y bien definidas. Para generar números aleatorios usando la Regla 30, se usa la columna de red central, a partir de la cual se selecciona una secuencia de nbits aleatorios, a partir de la cual se forma el nnúmero aleatorio de bits deseado . El siguiente número aleatorio se genera utilizando los siguientes nbits de la columna.


Generando números aleatorios usando la Regla 30

Si siempre comienza a seleccionar celdas de la primera línea, entonces la secuencia de números generada siempre será predecible. Y esto no es lo que necesitamos. Para crear números pseudoaleatorios, utilizaremos un valor inicial aleatorio (por ejemplo, la hora actual), omitiremos el número correspondiente de líneas y luego seleccionaremos secuencias denlíneas y crearemos números aleatorios basados ​​en ellas.

Los números pseudoaleatorios generados usando la Regla 30 no son criptográficamente seguros, pero son adecuados para simulaciones, hasta que usemos valores iniciales inapropiados como0.

Una de las principales ventajas de usar la Regla 30 para generar números pseudoaleatorios es que puede crear muchos números aleatorios en modo paralelo seleccionando aleatoriamente muchas columnas de longitud n bits. Aquí está un ejemplo de una secuencia pseudo-aleatoria de números de 8 bits generado por este método utilizando el valor inicial 0: 220, 197, 147, 174, 117, 97, 149, 171, 240, 241.

El valor inicial, además, se puede usar para establecer el estado inicial del modelo (línea No. 0). Como resultado, se pueden obtener números pseudoaleatorios simplemente eligiendonbit de la columna central, comenzando en la fila cero. Este enfoque es más efectivo, pero depende en gran medida de la calidad del valor inicial. Un valor inicial seleccionado incorrectamente puede dar lugar a la aparición de números bien pronosticados. Una demostración de este enfoque se puede encontrar aquí .

Regla 30 en el mundo real


La regla 30 se puede ver en la naturaleza, en forma de un patrón en el caparazón de la especie textil Conus de gasterópodos . La estación de tren Cambridge North está enmarcada por paneles que representan los resultados evolutivos de un modelo construido utilizando la Regla 30.

Resumen


Si encuentra interesante la Regla 30, le recomiendo escribir su propia simulación utilizando la biblioteca p5 . Este algoritmo se puede implementar de forma bastante general, lo que permitirá que el mismo programa genere patrones para diferentes reglas: 90, 110, 117, etc. Los patrones generados usando varias reglas son muy interesantes. Si quieres, puedes pasar al siguiente nivel. Puede expandir el modelo a tres dimensiones y explorar la evolución de los patrones. Creo que la programación puede traer mucho placer si tiene un componente visual.

Es sorprendente cuando dos campos de la ciencia aparentemente no relacionados, autómatas celulares y criptografía, se combinan para crear algo sorprendente. Aunque el algoritmo descrito aquí ya no se usa ampliamente debido a la aparición de algoritmos más eficientes, nos alienta a usar creativamente autómatas celulares.

¡Queridos lectores! ¿Qué generadores de números pseudoaleatorios usas?

More articles:


All Articles