Hispanopedia Wiki
La regla 30 es un autómata celular elemental introducido por Stephen Wolfram en 1983. [2] Usando el esquema de clasificación de Wolfram , la Regla 30 es una regla de Clase III, que muestra un comportamiento caótico aperiódico .
Esta regla es de particular interés porque produce patrones complejos, aparentemente aleatorios, a partir de reglas simples y bien definidas. Debido a esto, Wolfram cree que la Regla 30, y los autómatas celulares en general, son la clave para comprender cómo las reglas simples producen estructuras y comportamientos complejos en la naturaleza. Por ejemplo, un patrón parecido a la Regla 30 aparece en el caparazón de la especie de caracol cónico Conus textile , muy extendida . La Regla 30 también se ha utilizado como generador de números aleatorios en Mathematica [3] y también se ha propuesto como un posible cifrado de flujo para su uso en criptografía [4] [5] .
La regla 30 se llama así porque 30 es el código Wolfram más pequeño que describe su conjunto de reglas (como se describe a continuación). La imagen especular, el complemento y el complemento especular de la regla 30 tienen los códigos Wolfram 86, 135 y 149, respectivamente.
Conjunto de reglas
En todos los autómatas celulares elementales de Wolfram se considera una matriz unidimensional infinita de células autómatas celulares con sólo dos estados, cada una de las cuales se encuentra en un estado inicial. En intervalos de tiempo discretos, cada célula cambia de estado espontáneamente en función de su estado actual y del estado de sus dos vecinas. Para la regla 30, el conjunto de reglas que gobierna el siguiente estado del autómata es:
Si las celdas izquierda, central y derecha se denotan como (p,q,r), entonces la fórmula correspondiente para el siguiente estado de la celda central se puede expresar como p x o (q o r) . Se llama Regla 30 porque en binario , 00011110 2 = 30.
El siguiente diagrama muestra el patrón creado, con celdas coloreadas según el estado anterior de su vecindad. Los colores más oscuros representan "1" y los colores más claros representan "0". El tiempo aumenta hacia abajo en el eje vertical.
Estructura y propiedades
El siguiente patrón surge de un estado inicial en el que una sola celda con estado 1 (mostrada en negro) está rodeada por celdas con estado 0 (blanco).
Regla 30 autómata celular
Aquí, el eje vertical representa el tiempo y cualquier sección transversal horizontal de la imagen representa el estado de todas las células de la matriz en un punto específico de la evolución del patrón. Hay varios motivos presentes en esta estructura, como la aparición frecuente de triángulos blancos y un patrón de rayas bien definido en el lado izquierdo; sin embargo, la estructura en su conjunto no tiene un patrón discernible. El número de células negras en la generación viene dado por la secuencia
- 1, 3, 3, 6, 4, 9, 5, 12, 7, 12, 11, 14, 12, 19, 13, 22, 15, 19, ... (secuencia A070952 en la OEIS )
y es aproximadamente . [ cita requerida ]
Caos
La regla 30 cumple con las rigurosas definiciones de caos propuestas por Devaney y Knudson. En particular, según los criterios de Devaney, la regla 30 muestra una dependencia sensible de las condiciones iniciales (dos configuraciones iniciales que difieren solo en un pequeño número de celdas divergen rápidamente), sus configuraciones periódicas son densas en el espacio de todas las configuraciones, según la topología de Cantor en el espacio de configuraciones (existe una configuración periódica con cualquier patrón finito de celdas), y es mixta (para dos patrones finitos de celdas cualesquiera, existe una configuración que contiene un patrón que eventualmente conduce a una configuración que contiene el otro patrón). Según los criterios de Knudson, muestra una dependencia sensible y existe una órbita densa (una configuración inicial que eventualmente muestra cualquier patrón finito de celdas). Ambas caracterizaciones del comportamiento caótico de la regla se derivan de una propiedad más simple y fácil de verificar de la Regla 30: es permutativa por la izquierda , lo que significa que si dos configuraciones C y D difieren en el estado de una sola celda en la posición i , entonces después de un solo paso las nuevas configuraciones diferirán en la celda i + 1. [ 6]
Aplicaciones
Generación de números aleatorios
Como se puede apreciar en la imagen de arriba, la regla 30 genera una aparente aleatoriedad a pesar de la falta de algo que pueda considerarse razonablemente como una entrada aleatoria. Stephen Wolfram propuso utilizar su columna central como generador de números pseudoaleatorios (PRNG); pasa muchas pruebas estándar de aleatoriedad y Wolfram utilizó anteriormente esta regla en el producto Mathematica para crear números enteros aleatorios. [7]
Sipper y Tomassini han demostrado que, como generador de números aleatorios, la regla 30 muestra un comportamiento deficiente en una prueba de chi cuadrado cuando se aplica a todas las columnas de reglas en comparación con otros generadores basados en autómatas celulares. [8] Los autores también expresaron su preocupación de que "los resultados relativamente bajos obtenidos por el CA de la regla 30 pueden deberse al hecho de que consideramos N secuencias aleatorias generadas en paralelo, en lugar de la única considerada por Wolfram". [9]
Decoración
La estación de tren de Cambridge North está decorada con paneles arquitectónicos que muestran la evolución de la Regla 30 (o equivalentemente bajo inversión en blanco y negro, la Regla 135). [10] El arquitecto describió el diseño como inspirado en el Juego de la vida de Conway , un autómata celular diferente estudiado por el matemático de Cambridge John Horton Conway , pero que en realidad no está basado en la vida. [11] [12]
Programación
La actualización de estado se puede realizar rápidamente mediante operaciones bit a bit , si los valores de las celdas están representados por bits dentro de una (o más) palabras de computadora. Aquí se muestra en C++ :
#include <stdint.h> #include <iostream>
int main () { uint64_t estado = 1u << 31 ; para ( int i = 0 ; i < 32 ; ++ i ) { para ( int j = 64 ; j -- ;) { std :: cout << char ( estado >> j & 1 ? 'O' : '.' ); } std :: cout << '\n' ; estado = ( estado >> 1 ) ^ ( estado | estado << 1 ); } }
Este programa produce el siguiente resultado:
................................O................. .............. ..............................OOO.............................. ................................OO..O................ ............. .................................OO.OOOO.................. .......... ................................OO..O...O.......... ............. .........................OO.OOOO.OOO.................. ........ ..........................OO..O....OO..O.... ............. .........................OO.OOOO..OOOOOO.................. ..... ........................OO..O...OOO.....O............ ........... .............OO.OOOO.OO..O...OOO.......... ....... ........................OO..O....O.OOOO.OO..O............ ......... ..................OO.OOOO..OO.O....O.OOOO............... ...... .....................OO..O...OOO..OO..OO.O...O..... ......... ...................OO.OOOO.OO..OOO.OOO..OO.OOO................ .. ..................OO..O....O.OOO...O..OOO..O..O........ ......... .................OO.OOOO..OO.O..O.OOOOOO..OOOOOOOO................ ................OO..O...OOO..OOOO.O....OOO......O....... ...... .................OO.OOOO.OO..OOO....OO..OO..O....OOO.......... ... ..............OO..O....O.OOO..O..OO.OOO.OOOO..OO..O....... .... .............OO.OOOO..OO.O..OOOOOO..O...O...OOO.OOOO............. ............OO..O...OOO..OOOO.....OOOO.OOO.OO...O...O....... .. .........OO.OOOO.OO..OOO...O...OO....O...OOOOO.OOO.......... ..........OO..O....O.OOO..O.OOO.OO.O..OOO.OO.OO..O..O....... .. .........OO.OOOO..OO.O..OOO.O...O..OOOO...O..O.OO.OOOOOO........ ........OO..O...OOO..OOOO...OO.OOOOO...O.OOOOOO.O..O.....O....... .......OO.OOOO.OO..OOO...O.OO..O....O.OO.O.....OOOOOO...OOO...... ......OO..O....O.OOO..O.OO.O.OOOO..OO.O..OO...OO....O.OO..O.. ... .....OO.OOOO..OO.O..OOO.O..OO..OOO..OOOO.O.OO.O..OO.O.OOOO.... ....OO..O...OOO..OOOO...OOOO.OO.OO..OOO....OO.OOOO..OO..O... ...OO.OOOO.OO..OOO...O.OO....O..O.OOO..O..OO.OOOO...OOO.OO.OOO.. ..OO..O....O.OOO..O.OO.OO.OOOOOO.O..OOOOOO..O...O.OO...O..O..O. .OO.OOOO..OO.O..OOO.O..O.OOOO.....OOOO.....OOOO.OO.OOOOOOOOOOOO
Véase también
Referencias
- ^ Stephen Coombes (febrero de 2009). "La geometría y la pigmentación de las conchas marinas" (PDF) . www.maths.nottingham.ac.uk . Universidad de Nottingham . Consultado el 10 de abril de 2013 .
- ^ Wolfram, S. (1983). "Mecánica estadística de autómatas celulares". Rev. Mod. Phys . 55 (3): 601–644. Código Bibliográfico :1983RvMP...55..601W. doi :10.1103/RevModPhys.55.601.
- ^ "Generación de números aleatorios". Documentación de Wolfram Mathematica 8. Consultado el 31 de diciembre de 2011 .
- ^ Wolfram, S. (1985). "Criptografía con autómatas celulares". Actas de Advances in Cryptology – CRYPTO '85 . Apuntes de clase en informática 218, Springer-Verlag. pág. 429. doi :10.1007/3-540-39799-X_32.
- ^ Meier, Willi; Staffelbach, Othmar (1991). "Análisis de secuencias pseudoaleatorias generadas por autómatas celulares". Avances en criptología – Proc. Taller sobre la teoría y aplicación de técnicas criptográficas, EUROCRYPT '91 . Lecture Notes in Computer Science 547, Springer-Verlag. pág. 186. doi : 10.1007/3-540-46416-6_17 .
- ^ Cattaneo, Gianpiero; Finelli, Michele; Márgara, Luciano (2000). "Investigación del caos topológico mediante la dinámica de autómatas celulares elementales". Informática Teórica . 244 (1–2): 219–241. doi :10.1016/S0304-3975(98)00345-4. SEÑOR 1774395.
- ^ Lex Fridman (2 de marzo de 2018), MIT AGI: Computational Universe (Stephen Wolfram), archivado desde el original el 19 de diciembre de 2021 , consultado el 7 de marzo de 2018
- ^ Sipper, Moshe; Tomassini, Marco (1996). "Generación de generadores de números aleatorios paralelos mediante programación celular". Revista Internacional de Física Moderna C . 7 (2): 181–190. Bibcode :1996IJMPC...7..181S. doi :10.1142/S012918319600017X.
- ^ Página 6 de Sipper, Moshe; Tomassini, Marco (1996). "Generación de generadores de números aleatorios paralelos mediante programación celular". Revista Internacional de Física Moderna C . 7 (2): 181–190. Código Bibliográfico :1996IJMPC...7..181S. doi :10.1142/S012918319600017X.
- ^ Wolfram, Stephen (1 de junio de 2017), "¡Dios mío, está cubierto por la regla 30!", blog de Stephen Wolfram
- ^ Lawson-Perfect, Christian (23 de mayo de 2017), "Respuesta correcta para la razón equivocada: autómata celular en la nueva estación de Cambridge North", The Aperiodical
- ^ Purtill, Corinne. "El homenaje de una estación de tren del Reino Unido a un matemático famoso acertó en todo, excepto en sus matemáticas". Quartz . Consultado el 12 de junio de 2017 .
- Wolfram, Stephen, 1985, Criptografía con autómatas celulares , CRYPTO'85.
Enlaces externos
- Weisstein, Eric W. "Regla 30". MundoMatemático .
- "Anuncio de los premios Rule 30". Escritos de Stephen Wolfram . 1 de octubre de 2019.
- Regla 30 del atlas de autómatas celulares de Wolfram
- Regla 30: Generador de bits pseudoaleatorios de Wolfram. Receta 32 en Primordial Soup Kitchen de David Griffeath.
- Patrones de la regla 30 que se repiten. Lista de patrones que, cuando se repiten para llenar las celdas de un autómata de la regla 30, se repiten después de un número finito de pasos de tiempo. Frans Faase, 2003. Archivado desde el original el 8 de agosto de 2013
- Mosaico de pavimento fractal. Introducción básica al patrón de la Regla 30 desde la perspectiva del experto en software LOGO Olivier Schmidt-Chevalier.
- Charla TED de febrero de 2010. Stephen Wolfram habla sobre la computación, una teoría del todo donde menciona la regla 30, entre otras cosas.