En el estudio matemático de los autómatas celulares , Rule 90 es un autómata celular elemental basado en la función exclusiva o . Consiste en una matriz unidimensional de celdas, cada una de las cuales puede contener un valor 0 o 1. En cada paso de tiempo, todos los valores se reemplazan simultáneamente por el exclusivo o por sus dos valores vecinos. [1] Martin, Odlyzko y Wolfram (1984) lo llaman "el autómata celular no trivial más simple", [2] y se describe extensamente en el libro de 2002 de Stephen Wolfram A New Kind of Science . [3]
Cuando se parte de una sola célula viva, la Regla 90 tiene un diagrama espacio-temporal en forma de triángulo de Sierpiński . El comportamiento de cualquier otra configuración se puede explicar como una superposición de copias de este patrón, combinadas usando la función exclusiva o . Cualquier configuración con solo un número finito de celdas distintas de cero se convierte en un replicador que eventualmente llena la matriz con copias de sí mismo. Cuando la Regla 90 se inicia desde una configuración inicial aleatoria , su configuración permanece aleatoria en cada paso de tiempo. Su diagrama de tiempo-espacio forma muchas "ventanas" triangulares de diferentes tamaños, patrones que se forman cuando una fila consecutiva de celdas se vuelve simultáneamente cero y luego las celdas con valor 1 se mueven gradualmente a esta fila desde ambos extremos.
Algunos de los primeros estudios de la Regla 90 se realizaron en relación con un problema no resuelto de la teoría de números , la conjetura de Gilbreath , sobre las diferencias de números primos consecutivos . Esta regla también está relacionada con la teoría de números de una manera diferente, a través de la secuencia de Gould . Esta secuencia cuenta el número de celdas distintas de cero en cada paso de tiempo después de iniciar la Regla 90 con una sola celda viva. Sus valores son potencias de dos , con exponentes iguales al número de dígitos distintos de cero en la representación binaria del número de paso. Otras aplicaciones de la Regla 90 han incluido el diseño de tapices .
Cada configuración de Rule 90 tiene exactamente cuatro predecesores, otras configuraciones que forman la configuración dada después de un solo paso. Por lo tanto, a diferencia de muchos otros autómatas celulares como el Juego de la vida de Conway , la Regla 90 no tiene el Jardín del Edén , una configuración sin predecesores. Proporciona un ejemplo de un autómata celular que es sobreyectivo (cada configuración tiene un predecesor) pero no inyectivo (tiene conjuntos de más de una configuración con el mismo sucesor). Se deduce del teorema del Jardín del Edén que la Regla 90 es localmente inyectiva (todas las configuraciones con el mismo sucesor varían en un número infinito de celdas).
Descripción
Reglas
La regla 90 es un autómata celular elemental . Eso significa que consiste en una matriz unidimensional de celdas, cada una de las cuales tiene un solo valor binario, ya sea 0 o 1. Una asignación de valores a todas las celdas se llama configuración . El autómata recibe una configuración inicial y luego avanza a través de otras configuraciones en una secuencia de pasos de tiempo discretos. En cada paso, todas las celdas se actualizan simultáneamente. Una regla preespecificada determina el nuevo valor de cada celda en función de su valor anterior y de los valores en sus dos celdas vecinas. Todas las celdas obedecen a la misma regla, que puede darse como una fórmula o como una tabla de reglas que especifique el nuevo valor para cada posible combinación de valores vecinos. [1]
En el caso de la Regla 90, el nuevo valor de cada celda es el exclusivo o de los dos valores vecinos. De manera equivalente, el siguiente estado de este autómata en particular se rige por la siguiente tabla de reglas: [1]
patrón actual | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
---|---|---|---|---|---|---|---|---|
nuevo estado para la celda central | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
Nombrar
El nombre de la regla 90 proviene de Stephen Wolfram 's notación binaria-decimal para las reglas de autómata celular unidimensional. Para calcular la notación de la regla, concatene los nuevos estados de la tabla de reglas en un solo número binario y convierta el número en decimal : 01011010 2 = 90 10 . [1] La regla 90 también se ha llamado el autómata de Sierpiński , debido a la forma característica del triángulo de Sierpiński que genera, [4] y el autómata celular Martin-Odlyzko-Wolfram después de las primeras investigaciones de Olivier Martin, Andrew M. Odlyzko y Stephen. Wolfram ( 1984 ) sobre este autómata. [5]
Propiedades
Aditividad, superposición y descomposición
Una configuración en la Regla 90 se puede dividir en dos subconjuntos de celdas que no interactúan entre sí. Uno de estos dos subconjuntos consta de las celdas en posiciones pares en pasos de tiempo pares y las celdas en posiciones impares en pasos de tiempo impares. El otro subconjunto consiste en las celdas en posiciones pares en pasos de tiempo impares y las celdas en posiciones impares en pasos de tiempo pares. Cada uno de estos dos subconjuntos puede verse como un autómata celular con solo su mitad de las células. [6] La regla para el autómata dentro de cada uno de estos subconjuntos es equivalente (excepto por un cambio de media celda por paso de tiempo) a otro autómata celular elemental , Regla 102 , en el que el nuevo estado de cada celda es el exclusivo o de su antiguo estado y su vecino correcto. Es decir, el comportamiento de la Regla 90 es esencialmente el mismo que el comportamiento de dos copias intercaladas de la Regla 102. [7]
La regla 90 y la regla 102 se denominan autómatas celulares aditivos . Esto significa que, si se combinan dos estados iniciales calculando el exclusivo o de cada uno de sus estados, entonces sus configuraciones posteriores se combinarán de la misma manera. De manera más general, se puede dividir cualquier configuración de la Regla 90 en dos subconjuntos con celdas distintas de cero, hacer evolucionar los dos subconjuntos por separado y calcular cada configuración sucesiva del autómata original como exclusiva o de las configuraciones en los mismos pasos de tiempo de los dos subconjuntos. . [2]
Árboles atrofiados y claros triangulares
El autómata de la Regla 90 (en su forma equivalente en uno de los dos subconjuntos independientes de celdas alternas) se investigó a principios de la década de 1970, en un intento de obtener información adicional sobre la conjetura de Gilbreath sobre las diferencias de números primos consecutivos . En el triángulo de números generado a partir de los números primos aplicando repetidamente el operador de diferencia hacia adelante , parece que la mayoría de los valores son 0 o 2. En particular, la conjetura de Gilbreath afirma que los valores más a la izquierda en cada fila de este triángulo son todos 0 o 2. Cuando una subsecuencia contigua de valores en una fila del triángulo son todos 0 o 2, entonces la Regla 90 se puede usar para determinar la subsecuencia correspondiente en la siguiente fila. Miller (1970) explicó la regla mediante una metáfora del crecimiento de los árboles en un bosque, titulando su artículo sobre el tema "Bosques periódicos de árboles atrofiados". En esta metáfora, un árbol comienza a crecer en cada posición de la configuración inicial cuyo valor es 1, y este bosque de árboles luego crece simultáneamente, a una nueva altura sobre el suelo en cada paso de tiempo. Cada celda distinta de cero en cada paso de tiempo representa una posición que está ocupada por una rama de árbol en crecimiento. En cada paso de tiempo sucesivo, una rama puede crecer hasta convertirse en una de las dos celdas por encima de ella a su izquierda y derecha solo cuando no hay otra rama compitiendo por la misma celda. Un bosque de árboles que crecen de acuerdo con estas reglas tiene exactamente el mismo comportamiento que la Regla 90. [8]
A partir de cualquier configuración inicial de la Regla 90, se puede formar un bosque matemático , un gráfico acíclico dirigido en el que cada vértice tiene como máximo un borde saliente, cuyos árboles son los mismos que los árboles en la metáfora de Miller. El bosque tiene un vértice para cada par ( x , i ) tal que la celda x es distinta de cero en el momento i . Los vértices en el tiempo 0 no tienen bordes salientes; cada uno forma la raíz de un árbol en el bosque. Para cada vértice ( x , i ) con i distinto de cero, su borde de salida va a ( x ± 1, i - 1) , el único vecino distinto de cero de x en el paso de tiempo i - 1 . Miller observó que estos bosques desarrollan "claros" triangulares, regiones del diagrama espacio-temporal sin celdas distintas de cero delimitadas por un borde inferior plano y lados diagonales. Este claro se forma cuando una secuencia consecutiva de células se vuelve cero simultáneamente en un paso de tiempo, y luego (en la metáfora del árbol) las ramas crecen hacia adentro, y eventualmente vuelven a cubrir las células de la secuencia. [8]
Para condiciones iniciales aleatorias, los límites entre los árboles formados de esta manera cambian ellos mismos en un patrón aparentemente aleatorio, y los árboles frecuentemente mueren por completo. Pero por medio de la teoría de los registros de desplazamiento, él y otros pudieron encontrar las condiciones iniciales en las que todos los árboles permanecen vivos para siempre, el patrón de crecimiento se repite periódicamente y se puede garantizar que todos los claros permanecerán limitados en tamaño. [8] [9] Miller utilizó estos patrones repetidos para formar los diseños de tapices . Algunos de los tapices de Miller representan árboles físicos; otros visualizan el autómata de la Regla 90 usando patrones abstractos de triángulos. [8]
Triángulo de Sierpiński
El diagrama tiempo-espacio de la Regla 90 es un gráfico en el que la i- ésima fila registra la configuración del autómata en el paso i . Cuando el estado inicial tiene una sola celda distinta de cero, este diagrama tiene la apariencia del triángulo de Sierpiński , un fractal formado por la combinación de triángulos en triángulos más grandes. Las reglas 18, 22, 26, 82, 146, 154, 210 y 218 también generan triángulos de Sierpinski a partir de una sola celda, sin embargo, no todos se crean de manera completamente idéntica. Una forma de explicar esta estructura utiliza el hecho de que, en la Regla 90, cada celda es la exclusiva o de sus dos vecinas. Debido a que esto es equivalente a la suma módulo -2, esto genera la versión módulo 2 del triángulo de Pascal . El diagrama tiene un 1 donde el triángulo de Pascal tiene un número impar y un 0 donde el triángulo de Pascal tiene un número par . Esta es una versión discreta del triángulo de Sierpiński. [1] [10]
El número de células vivas en cada fila de este patrón es una potencia de dos . En la i- ésima fila, es igual a 2 k , donde k es el número de dígitos distintos de cero en la representación binaria del número i . La secuencia de estos números de células vivas,
- 1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, ... (secuencia A001316 en la OEIS )
se conoce como secuencia de Gould . La única celda viva de la configuración inicial es un patrón de diente de sierra . Esto significa que, en algunos pasos, el número de células vivas crece arbitrariamente, mientras que en otros regresan a sólo dos células vivas, con una frecuencia infinita. La tasa de crecimiento de este patrón tiene una forma de onda de diente de sierra de crecimiento característica que puede usarse para reconocer procesos físicos que se comportan de manera similar a la Regla 90. [4]
El triángulo de Sierpiński también ocurre de una manera más sutil en la evolución de cualquier configuración en la Regla 90. En cualquier momento i en la evolución de la Regla, el estado de cualquier celda se puede calcular como el exclusivo o de un subconjunto de las celdas en el Configuracion inicial. Ese subconjunto tiene la misma forma que la i- ésima fila del triángulo de Sierpiński. [11]
Replicación
En el triángulo de Sierpiński, para cualquier entero i , las filas numeradas por múltiplos de 2 i tienen celdas distintas de cero espaciadas al menos 2 i unidades. Por lo tanto, debido a la propiedad aditiva de la Regla 90, si una configuración inicial consiste en un patrón finito P de celdas distintas de cero con un ancho menor que 2 i , entonces en pasos que son múltiplos de 2 i , la configuración consistirá en copias de P espaciadas al menos 2 i unidades de principio a fin. Este espacio es lo suficientemente amplio para evitar que las copias interfieran entre sí. El número de copias es el mismo que el número de celdas distintas de cero en la fila correspondiente del triángulo de Sierpiński. Por lo tanto, en esta regla, cada patrón es un replicador : genera múltiples copias de sí mismo que se extienden a lo largo de la configuración y eventualmente llenan toda la matriz. Otras reglas, incluido el constructor universal de Von Neumann , el autómata celular de Codd y los bucles de Langton, también tienen replicadores que funcionan llevando y copiando una secuencia de instrucciones para construirse ellos mismos. Por el contrario, la réplica de la Regla 90 es trivial y automática. [12]
Predecesores y jardines del Edén
En la Regla 90, en un entramado unidimensional infinito, cada configuración tiene exactamente cuatro configuraciones predecesoras. Esto se debe a que, en un predecesor, dos celdas consecutivas cualesquiera pueden tener cualquier combinación de estados, pero una vez que se eligen los estados de esas dos celdas, solo hay una opción consistente para los estados de las celdas restantes. Por lo tanto, no hay Jardín del Edén en la Regla 90, una configuración sin predecesores. La configuración de la Regla 90 que consta de una sola celda distinta de cero (con todas las demás celdas cero) no tiene predecesores que tengan un número finito de no ceros. Sin embargo, esta configuración no es un Jardín del Edén porque tiene predecesores con infinitos no ceros. [13]
El hecho de que cada configuración tenga un predecesor puede resumirse diciendo que la Regla 90 es sobreyectiva . La función que asigna cada configuración a su sucesora es, matemáticamente, una función sobreyectiva. La regla 90 tampoco es inyectiva . En una regla inyectiva, cada dos configuraciones diferentes tienen diferentes sucesores, pero la Regla 90 tiene pares de configuraciones con el mismo sucesor. La regla 90 proporciona un ejemplo de un autómata celular que es sobreyectivo pero no inyectivo. El teorema del Jardín del Edén de Moore y Myhill implica que todo autómata celular inyectivo debe ser sobreyectivo, pero este ejemplo muestra que lo contrario no es cierto. [13] [14]
Debido a que cada configuración tiene solo un número limitado de predecesores, la evolución de la Regla 90 conserva la entropía de cualquier configuración. En particular, si se selecciona una configuración inicial infinita eligiendo el estado de cada celda de forma independiente al azar, siendo cada uno de los dos estados con la misma probabilidad de ser seleccionado, entonces cada configuración subsiguiente puede describirse exactamente con la misma distribución de probabilidad. [2]
Emulación por otros sistemas
Muchos otros autómatas celulares y otros sistemas computacionales son capaces de emular el comportamiento de la Regla 90. Por ejemplo, una configuración en la regla 90 puede traducirse en una configuración en los diferentes autómatas celulares elementales Regla 22. La traducción reemplaza cada celda de la Regla 90 por tres celdas consecutivas de la Regla 22. Estas celdas son todas cero si la celda de la Regla 90 es cero en sí misma. Una celda de la Regla 90 distinta de cero se traduce en un uno seguido de dos ceros. Con esta transformación, cada seis pasos del autómata de la Regla 22 simula un solo paso del autómata de la Regla 90. Simulaciones directas similares de la Regla 90 también son posibles para los autómatas celulares elementales Regla 45 y Regla 126, para ciertos sistemas de reescritura de cadenas y sistemas de etiquetas , y en algunos autómatas celulares bidimensionales, incluido Wireworld . La regla 90 también puede simularse a sí misma de la misma manera. Si cada celda de una configuración de la Regla 90 se reemplaza por un par de celdas consecutivas, la primera contiene el valor de la celda original y la segunda contiene cero, entonces esta configuración duplicada tiene el mismo comportamiento que la configuración original a la mitad de la velocidad. [15]
Se sabe que varios otros autómatas celulares admiten replicadores, patrones que hacen copias de sí mismos, y la mayoría comparte el mismo comportamiento que en el modelo de crecimiento del árbol para la Regla 90. Se coloca una nueva copia a cada lado del patrón del replicador, siempre que el el espacio allí está vacío. Sin embargo, si dos replicadores intentan copiarse a sí mismos en la misma posición, el espacio permanece en blanco. En cualquier caso, los mismos replicadores desaparecen, dejando que sus copias continúen con la replicación. Un ejemplo estándar de este comportamiento es el patrón de "pasta de pajarita" en la regla bidimensional HighLife . Esta regla se comporta de muchas maneras como el Juego de la vida de Conway, pero un replicador tan pequeño no existe en Life. Siempre que un autómata admita replicadores con el mismo patrón de crecimiento, se pueden usar matrices unidimensionales de replicadores para simular la Regla 90. [16] La regla 90 (en filas finitas de celdas) también se puede simular mediante los osciladores de bloque de dos dimensiones. El autómata celular realista B36 / S125, también llamado "2x2", y el comportamiento de la Regla 90 se pueden utilizar para caracterizar los posibles períodos de estos osciladores. [17]
Ver también
- Otros autómatas celulares elementales: Regla 30 , Regla 110 y Regla 184
Referencias
- ^ a b c d e Wolfram, Stephen (1983), "Mecánica estadística de los autómatas celulares" , Reseñas de la física moderna , 55 (3): 601–644, Bibcode : 1983RvMP ... 55..601W , doi : 10.1103 / RevModPhys.55.601.
- ^ a b c Martin, Olivier; Odlyzko, Andrew M .; Wolfram, Stephen (1984), "Propiedades algebraicas de los autómatas celulares" , Communications in Mathematical Physics , 93 (2): 219–258, Bibcode : 1984CMaPh..93..219M , doi : 10.1007 / BF01223745.
- ^ Wolfram, Stephen (2002), Un nuevo tipo de ciencia , Wolfram Media. El índice del libro enumera más de 50 subtemas distintos para la Regla 90.
- ^ a b Claussen, Jens Christian; Nagler, Jan; Schuster, Heinz Georg (2004), "La señal de Sierpinski genera espectros de 1 ∕ f α ", Physical Review E , 70 (3): 032101, arXiv : cond-mat / 0308277 , Bibcode : 2004PhRvE..70c2101C , doi : 10.1103 / PhysRevE .70.032101 , PMID 15524560 .
- ^ Misiurewicz, Michał; Stevens, John G .; Thomas, Diana M. (2006), "Iteraciones de mapas lineales sobre campos finitos", Álgebra lineal y sus aplicaciones , 413 (1): 218-234, doi : 10.1016 / j.laa.2005.09.002.
- ^ McIntosh, Harold V. (1993), Ancestors: Commentaries on "The Global Dynamics of Cellular Automata" por Andrew Wuensche y Mike Lesser (Addison-Wesley, 1992) (PDF) , Instituto de Ciencias, Universidad Autónoma de Puebla.
- ^ Kawaharada, Akane (2014), "El autómata celular de Ulam y la regla 150", Hokkaido Mathematical Journal , 43 (3): 361–383, doi : 10.14492 / hokmj / 1416837570 , MR 3282639: "A excepción de las CA triviales, las otras cuatro CA elementales lineales, Regla 60, Regla 90, Regla 102 y Regla 150, son esencialmente equivalentes a la Regla 90 o la Regla 150".
- ^ a b c d Miller, JCP (1970), "Bosques periódicos de árboles atrofiados", Transacciones filosóficas de la Royal Society of London , Serie A, Ciencias matemáticas y físicas, 266 (1172): 63–111, Bibcode : 1970RSPTA.266 ... 63M , doi : 10.1098 / rsta.1970.0003 , JSTOR 73779.
- ^ ApSimon, HG (1970), "Bosques periódicos cuyos claros más grandes son de tamaño 3", Transacciones filosóficas de la Royal Society of London , Serie A, Ciencias matemáticas y físicas, 266 (1172): 113-121, Bibcode : 1970RSPTA.266 ..113A , doi : 10.1098 / rsta.1970.0004 , JSTOR 73780; ApSimon, HG (1970), "Bosques periódicos cuyos claros más grandes son de tamaño n ≥ 4", Transacciones filosóficas de la Royal Society of London , Serie A, Ciencias matemáticas y físicas, 266 (1538): 399–404, Bibcode : 1970RSPSA .319..399A , doi : 10.1098 / rspa.1970.0185 , JSTOR 73780. Un análisis similar de configuraciones periódicas en la Regla 90 también aparece en Wolfram (2002) , p. 954.
- ^ Wolfram (2002) , págs. 25-26, 270-271, 870.
- ^ Kar, BK; Gupta, A .; Chaudhuri, P. Pal (1993), "Sobre expresiones explícitas en la teoría aditiva de autómatas celulares", Ciencias de la información , 72 (1–2): 83–103, doi : 10.1016 / 0020-0255 (93) 90030-P.
- ^ Waksman, Abraham (1969), "A model of replication", Journal of the ACM , 16 (1): 178–188, doi : 10.1145 / 321495.321509; Amoroso, Serafino; Cooper, Gerald (1971), "Estructuras de teselación para la reproducción de patrones arbitrarios", Journal of Computer and System Sciences , 5 (5): 455–464, doi : 10.1016 / S0022-0000 (71) 80009-0. Wolfram (1983) (figura 33 y texto circundante) también menciona la misma propiedad y, además de citar a Waksman, Amoroso y Cooper, atribuye su observación a un trabajo inédito de Edward Fredkin en 1981.
- ^ a b Skyum, Sven (1975), "Confusion in the Garden of Eden", Proceedings of the American Mathematical Society , 50 (1): 332–336, doi : 10.1090 / S0002-9939-1975-0386350-1
- ^ Sutner, Klaus (1991), "Gráficos de De Bruijn y autómatas celulares lineales" (PDF) , Sistemas complejos , 5 : 19-30. Wolfram (2002) , págs. 959–960. Martin, Odlyzko y Wolfram (1984) proporcionan un análisis similar de los predecesores de la misma regla para conjuntos finitos de celdas con condiciones de contorno periódicas.
- ^ Wolfram (2002) , págs. 269–270, 666–667, 701–702, 1117.
- ^ Griffeath, David (1996), "Receta para la semana del 1 al 7 de julio: Replicando a Skeeters", The Primordial Soup Kitchen.
- ^ Johnston, Nathaniel (2010), "The B36 / S125" 2x2 "Life-like cell autómata", en Adamatzky, Andrew (ed.), Game of Life Cellular Automata , Springer-Verlag, págs. 99-114, arXiv : 1203.1644 , Bibcode : 2010golc.book ... 99J , doi : 10.1007 / 978-1-84996-217-9_7.
enlaces externos
- Weisstein, Eric W. , "Regla 90" , MathWorld
- Regla 90 en el atlas de autómatas celulares de Wolfram