Regla 90

[1] Martin, Odlyzko y Wolfram (1984) lo llaman «el autómata celular no trivial más simple»,[2] y se describe ampliamente en el libro de Stephen Wolfram de 2002 A New Kind of Science.

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.

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.

Una asignación de valores a todas las celdas se denomina configuración.

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.

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.

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.

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.

[8][9] Miller utilizó estos patrones repetitivos para formar los diseños de los tapices.

Ese subconjunto tiene la misma forma que la fila i-ésima del triángulo de Sierpiński.

[11] En el triángulo de Sierpiński, para cualquier número entero i, las filas numeradas por múltiplos de 2i tienen celdas no nulas separadas al menos 2i unidades.

Este espaciado es lo suficientemente amplio como para evitar que las copias interfieran entre sí.

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.

Por lo tanto, no hay Jardín del Edén en la Regla 90, una configuración sin predecesores.

Sin embargo, esta configuración no es un Jardín del Edén porque tiene predecesores con infinitos nonzeros.

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.

Una nueva copia se coloca a cada lado del patrón replicador, siempre y cuando el espacio allí esté vacío.