# Regla 90

En el estudio matemático de los autómatas celulares, la regla 90 es un autómata celular elemental basado en el o exclusivo o función. Consiste en una matriz unidimensional de celdas, cada una de las cuales puede contener un valor 0 o 1. En cada paso temporal, todos los valores se sustituyen simultáneamente por el XOR de sus dos valores vecinos. Martin, Odlyzko y Wolfram (1984) lo llaman «el autómata celular no trivial más simple», y se describe ampliamente en el libro de Stephen Wolfram de 2002 A New Kind of Science.
Cuando se parte de una única 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 puede explicarse como una superposición de copias de este patrón, combinadas mediante la función exclusiva. Cualquier configuración con sólo finitamente muchas células distintas de cero se convierte en un replicador que eventualmente llena la matriz con copias de sí mismo. Cuando la regla 90 se inicia a partir de una configuración inicial aleatoria, su configuración sigue siendo aleatoria en cada paso temporal. Su diagrama espacio-temporal forma muchas «ventanas» triangulares de diferentes tamaños, patrones que se forman cuando una fila consecutiva de celdas se convierte simultáneamente en cero y entonces las celdas con valor 1 se mueven gradualmente hacia esta fila desde ambos extremos.
Algunos de los primeros estudios sobre 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 otra forma, a través de la secuencia de Gould. Esta secuencia cuenta el número de células distintas de cero en cada paso de tiempo después de iniciar la regla 90 con una sola célula 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 la Regla 90 tiene exactamente cuatro predecesoras, 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 Jardín del Edén, una configuración sin predecesores. Proporciona un ejemplo de autómata celular que es sobreyectiva (cada configuración tiene un predecesor) pero no inyectivo (tiene conjuntos de más de una configuración con el mismo sucesor). Del teorema del Jardín del Edén se deduce 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. Esto significa que consiste en una matriz unidimensional de celdas, cada una de las cuales contiene un único valor binario, 0 o 1. Una asignación de valores a todas las celdas se denomina configuración. Una asignación de valores a todas las celdas se denomina configuración. El autómata recibe una configuración inicial y va pasando por otras configuraciones en una secuencia de pasos temporales discretos. En cada paso, todas las celdas se actualizan simultáneamente. Una regla preestablecida determina el nuevo valor de cada celda en función de su valor anterior y de los valores de sus dos celdas vecinas. Todas las celdas obedecen la misma regla, que puede presentarse como una fórmula o como una tabla de reglas que especifica el nuevo valor para cada combinación posible de valores vecinos.
En el caso de la regla 90, el nuevo valor de cada celda es el o exclusivo de los dos valores vecinos. Equivalentemente, el siguiente estado de este autómata en particular se rige por la siguiente tabla de reglas:
| Patrón actual | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
| Nuevo estado para la célula central | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |

### Nombre

El nombre de la regla 90 procede de la notación binaria-decimal de Stephen Wolfram para reglas de autómatas celulares unidimensionales. Para calcular la notación de la regla, concatene los nuevos estados de la tabla de reglas en un único número binario y convierta el número en decimal: 010110102 = 9010. La regla 90 también se ha denominado autómata de Sierpiński, debido a la característica forma de triángulo de Sierpiński que genera, y autómata celular de Martin-Odlyzko-Wolfram por las primeras investigaciones de Olivier Martin, Andrew M. Odlyzko y Stephen Wolfram (1984) sobre este autómata.

## Propiedades
### Aditividad, superposición y descomposición

Una configuración de la regla 90 puede dividirse en dos subconjuntos de celdas que no interactúan entre sí. Uno de estos dos subconjuntos está formado por las celdas en posiciones pares en pasos de tiempo pares y las celdas en posiciones impares en pasos de tiempo impares. El otro subconjunto está formado por las células en posiciones pares en pasos de tiempo impares y las células en posiciones impares en pasos de tiempo pares. Cada uno de estos dos subconjuntos puede verse como un autómata celular con sólo su mitad de celdas. La regla para el autómata dentro de cada uno de estos subconjuntos es equivalente (excepto por un desplazamiento de media celda por paso de tiempo) a otro autómata celular elemental, la Regla 102, en la que el nuevo estado de cada celda es el exclusivo o de su antiguo estado y su vecino derecho. Es decir, el comportamiento de la Regla 90 es esencialmente el mismo que el de dos copias intercaladas de la Regla 102.
Las reglas 90 y 102 se denominan autómatas celulares aditivos. Esto significa que, si dos estados iniciales se combinan calculando la o exclusiva de cada uno de sus estados, sus configuraciones posteriores se combinarán de la misma manera. En términos más generales, 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 la o exclusiva de las configuraciones en los mismos pasos temporales de los dos subconjuntos.

### Á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 los años 70, 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 generados a partir de los primos aplicando repetidamente el operador de diferencia hacia delante, parece que la mayoría de los valores son 0 o 2. En concreto, la conjetura de Gilbreath afirma que los valores situados más a la izquierda de 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 se puede utilizar la regla 90 para determinar la subsecuencia correspondiente en la fila siguiente. Miller (1970) explicó la regla mediante una metáfora del crecimiento de un árbol 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 crece entonces simultáneamente, hasta una nueva altura sobre el suelo en cada paso temporal. Cada celda distinta de cero en cada paso temporal representa una posición ocupada por una rama creciente del árbol. En cada paso sucesivo, una rama puede crecer hacia una de las dos celdas situadas a su izquierda y derecha sólo cuando no haya otra rama compitiendo por la misma celda. Un bosque de árboles que crece según estas reglas tiene exactamente el mismo comportamiento que la regla 90.
A partir de cualquier configuración inicial de la Regla 90, se puede formar un bosque matemático, un grafo acíclico dirigido en el que cada vértice tiene como máximo una arista saliente, cuyos árboles son los mismos que los árboles de la metáfora de Miller. El bosque tiene un vértice por cada par (x,i) tal que la celda x es distinta de cero en el tiempo i. Los vértices en el tiempo 0 no tienen aristas 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 arista saliente se dirige 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 no nulas delimitadas por un borde inferior plano y lados diagonales. Un claro de este tipo se forma cuando una secuencia consecutiva de celdas se hace cero simultáneamente en un paso de tiempo, y entonces (en la metáfora del árbol) las ramas crecen hacia dentro, volviendo a cubrir finalmente las celdas de la secuencia.
En condiciones iniciales aleatorias, los límites entre los árboles formados de este modo se desplazan siguiendo un patrón aparentemente aleatorio, y con frecuencia los árboles mueren por completo. Sin embargo, gracias a la teoría de los registros de desplazamiento, él y otros fueron capaces de encontrar 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 permanecen limitados en tamaño. Miller utilizó estos patrones repetitivos para formar los diseños de los tapices. Algunos de los tapices de Miller representan árboles físicos; otros visualizan el autómata de la Regla 90 mediante patrones abstractos de triángulos.

### Triángulo de Sierpinski

El diagrama espacio-temporal de la regla 90 es un gráfico en el que la fila i registra la configuración del autómata en el paso i. Cuando el estado inicial tiene una única 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 única celda, sin embargo no todas ellas se crean de forma completamente idéntica. Una forma de explicar esta estructura utiliza el hecho de que, en la regla 90, cada celda es la o exclusiva de sus dos vecinas. Como esto es equivalente a la suma en módulo 2, se genera la versión en módulo 2 del triángulo de Pascal. El diagrama tiene un 1 siempre que el triángulo de Pascal tiene un número impar, y un 0 siempre que el triángulo de Pascal tiene un número par. Esta es una versión discreta del triángulo de Sierpiński.
El número de células vivas en cada fila de este patrón es una potencia de dos. En la fila i-ésima, 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, 4, 8, 4, 8, 8, 16, 2, 4, 4, 4, 4, 8, 8, 16, 4, 8, 8, 16, 16, 16, 32, … (secuencia A001316 en la OEIS)
Se conoce como secuencia de Gould. La única célula viva de la configuración inicial es un patrón en diente de sierra. Esto significa que en algunos pasos temporales el número de células vivas crece de forma arbitraria, mientras que en otros vuelve a ser de sólo dos células vivas, con una frecuencia infinita. La tasa de crecimiento de este patrón tiene una forma característica de onda creciente en diente de sierra que puede utilizarse para reconocer procesos físicos que se comportan de forma similar a la Regla 90.
El triángulo de Sierpiński también se produce de forma más sutil en la evolución de cualquier configuración de la Regla 90. En cualquier paso de tiempo i en la evolución de la Regla, el estado de cualquier celda puede calcularse como el exclusivo o de un subconjunto de las celdas de la configuración inicial. Ese subconjunto tiene la misma forma que la fila i-ésima del triángulo de Sierpiński.

### Replicación

En el triángulo de Sierpiński, para cualquier número entero i, las filas numeradas por múltiplos de 2$^i$ tienen celdas no nulas separadas 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 no nulas con anchura 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 inicio a inicio. Este espaciado es lo suficientemente amplio como 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. Así, en esta regla, cada patrón es un replicador: genera múltiples copias de sí mismo que se extienden por la configuración, llenando finalmente toda la matriz. Otras reglas, como 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 a sí mismos. En cambio, la replicación en la regla 90 es trivial y automática.

### 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 una predecesora, dos celdas consecutivas cualesquiera pueden tener cualquier combinación de estados, pero una vez elegidos los estados de esas dos celdas, sólo hay una elección coherente 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 consiste en una única celda distinta de cero (con todas las demás celdas iguales a 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 nonzeros.
El hecho de que cada configuración tenga un predecesor puede resumirse diciendo que la regla 90 es suryectiva. La función que asigna cada configuración a su sucesora es, matemáticamente, una función suryectiva. La regla 90 tampoco es inyectiva. En una regla inyectiva, cada dos configuraciones diferentes tienen sucesores diferentes, pero la regla 90 tiene pares de configuraciones con el mismo sucesor. La regla 90 es un ejemplo de autómata celular suryectivo pero no inyectivo. El teorema del Jardín del Edén de Moore y Myhill implica que todo autómata celular inyectivo debe ser suryectivo, pero este ejemplo muestra que lo contrario no es cierto.
Dado que cada configuración sólo tiene un número limitado de predecesoras, la evolución de la regla 90 preserva la entropía de cualquier configuración. En particular, si se selecciona una configuración inicial infinita eligiendo el estado de cada celda independientemente al azar, con cada uno de los dos estados con la misma probabilidad de ser seleccionado, entonces cada configuración posterior puede ser descrita exactamente por la misma distribución de probabilidad.

## 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 el autómata celular elemental diferente Regla 22. La traducción sustituye 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 a su vez cero. Una celda no nula de la Regla 90 se traduce en un uno seguido de dos ceros. Con esta transformación, cada seis pasos del autómata de la Regla 22 simulan un único 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 del mismo modo. Si cada celda de una configuración de la Regla 90 se sustituye por un par de celdas consecutivas, la primera de las cuales 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 velocidad.
Se conocen otros autómatas celulares que admiten replicadores, patrones que hacen copias de sí mismos, y la mayoría comparten el mismo comportamiento que en el modelo de crecimiento arbóreo de la regla 90. Una nueva copia se coloca a cada lado del patrón replicador, siempre y cuando el espacio allí esté vacío. Sin embargo, si dos replicadores intentan copiarse a sí mismos en la misma posición, entonces el espacio permanece vacío. En cualquier caso, los propios replicadores desaparecen, dejando que sus copias continúen la replicación. Un ejemplo estándar de este comportamiento es el patrón de «pasta de pajarita» de la regla bidimensional HighLife. Esta regla se comporta en muchos aspectos como el Juego de la Vida de Conway, pero un replicador tan pequeño no existe en la Vida. Siempre que un autómata admita replicadores con el mismo patrón de crecimiento, pueden utilizarse matrices unidimensionales de replicadores para simular la regla 90. La regla 90 (en filas finitas de celdas) también puede simularse mediante los osciladores de bloque del autómata celular bidimensional similar a Life B36/S125, también llamado «2x2», y el comportamiento de la regla 90 puede utilizarse para caracterizar los posibles periodos de estos osciladores.