El autómata celular de la Regla 110 (a menudo llamado simplemente Regla 110 ) [a] es un autómata celular elemental con un comportamiento interesante en el límite entre la estabilidad y el caos. En este sentido, es similar al Juego de la vida de Conway . Al igual que el Juego de la vida, se sabe que la Regla 110 con un patrón de fondo repetitivo particular es Turing completo . [2] Esto implica que, en principio, cualquier cálculo o programa de computadora puede simularse utilizando este autómata.
En un autómata celular elemental, un patrón unidimensional de 0 y 1 evoluciona según un conjunto simple de reglas. Que un punto del patrón sea 0 o 1 en la nueva generación depende de su valor actual, así como de los de sus dos vecinos.
El autómata de la regla 110 tiene el siguiente conjunto de reglas:
El nombre "Regla 110" deriva del hecho de que esta regla se puede resumir en la secuencia binaria 01101110; interpretada como un número binario , esto corresponde al valor decimal 110. Este es el esquema de nombres del código Wolfram .
En 2004, Matthew Cook publicó una prueba de que la Regla 110 con un patrón de fondo repetitivo particular es Turing completa , es decir, capaz de computación universal , que Stephen Wolfram había conjeturado en 1985. [2] Cook presentó su prueba en la conferencia CA98 del Instituto Santa Fe antes de la publicación del libro de Wolfram Un nuevo tipo de ciencia . Esto resultó en un asunto legal basado en un acuerdo de confidencialidad con Wolfram Research . [3] Wolfram Research bloqueó la publicación de la prueba de Cook durante varios años. [4]
Entre los 88 posibles autómatas celulares elementales únicos , la Regla 110 es la única para la que se ha demostrado directamente la completitud de Turing, aunque las pruebas de varias reglas similares se desprenden como corolarios simples (por ejemplo, la Regla 124, que es la reflexión horizontal de la Regla 110). La Regla 110 es posiblemente el sistema completo de Turing más simple conocido. [2] [5]
La regla 110, al igual que el Juego de la Vida , exhibe lo que Wolfram llama “ comportamiento de clase 4 ”, que no es ni completamente estable ni completamente caótico. Aparecen estructuras localizadas que interactúan de maneras complejas. [6]
Matthew Cook demostró que la Regla 110 es capaz de soportar el cómputo universal mediante la emulación sucesiva de sistemas de etiquetas cíclicas , luego de sistemas de 2 etiquetas y luego de máquinas de Turing . La etapa final tiene una sobrecarga de tiempo exponencial porque la cinta de la máquina de Turing está codificada con un sistema numérico unario . Neary y Woods (2006) presentaron una construcción diferente que reemplaza los sistemas de 2 etiquetas con máquinas de Turing en el sentido de las agujas del reloj y tiene una sobrecarga polinómica . [7]
Matthew Cook presentó su prueba de la universalidad de la regla 110 en una conferencia del Instituto Santa Fe, celebrada antes de la publicación de Un nuevo tipo de ciencia . Wolfram Research afirmó que esta presentación violaba el acuerdo de confidencialidad de Cook con su empleador, y obtuvo una orden judicial que excluía el artículo de Cook de las actas publicadas de la conferencia. No obstante, la existencia de la prueba de Cook se hizo conocida. El interés en su prueba no surgió tanto de su resultado como de sus métodos, específicamente de los detalles técnicos de su construcción. [8] El carácter de la prueba de Cook difiere considerablemente de la discusión de la regla 110 en Un nuevo tipo de ciencia . Cook ha escrito desde entonces un artículo que expone su prueba completa. [2]
Cook demostró que la Regla 110 era universal (o Turing completa) al mostrar que era posible usar la regla para emular otro modelo computacional, el sistema de etiquetas cíclicas , que se sabe que es universal. Primero aisló una serie de naves espaciales , patrones localizados autoperpetuantes, que podían construirse sobre un patrón que se repetía infinitamente en un universo de la Regla 110. Luego ideó una forma para que las combinaciones de estas estructuras interactuaran de una manera que pudiera explotarse para la computación.
La función de la máquina universal de la regla 110 requiere que se incorpore una cantidad finita de patrones localizados dentro de un patrón de fondo que se repite infinitamente. El patrón de fondo tiene catorce celdas de ancho y se repite exactamente cada siete iteraciones. El patrón es 00010011011111 .
En la máquina universal de la Regla 110, son de particular importancia tres patrones localizados. Se muestran en la imagen de abajo, rodeados por el patrón de fondo repetitivo. La estructura situada más a la izquierda se desplaza dos celdas hacia la derecha y se repite cada tres generaciones. Comprende la secuencia 0001110111 rodeada por el patrón de fondo que se muestra arriba, así como dos evoluciones diferentes de esta secuencia.
En las figuras, el tiempo transcurre de arriba a abajo: la línea superior representa el estado inicial y cada línea siguiente, el estado en el momento siguiente.
La estructura central se desplaza ocho celdas hacia la izquierda y se repite cada treinta generaciones. Comprende la secuencia 1001111 rodeada por el patrón de fondo indicado anteriormente, así como veintinueve evoluciones diferentes de esta secuencia.
La estructura situada más a la derecha permanece estacionaria y se repite cada siete generaciones. Comprende la secuencia 111 rodeada por el patrón de fondo indicado anteriormente, así como cinco evoluciones diferentes de esta secuencia.
A continuación se muestra una imagen que muestra las dos primeras estructuras pasando una a través de la otra sin interactuar más que por traslación (izquierda) e interactuando para formar la tercera estructura (derecha).
Hay muchas otras naves espaciales en la Regla 110, pero no aparecen tan prominentemente en la prueba de universalidad.
La maquinaria del sistema de etiquetas cíclicas tiene tres componentes principales:
El espaciamiento inicial entre estos componentes es de suma importancia. Para que el autómata celular implemente el sistema de etiquetas cíclicas, las condiciones iniciales del autómata deben seleccionarse cuidadosamente de modo que las diversas estructuras localizadas contenidas en él interactúen de manera altamente ordenada.
La cadena de datos en el sistema de etiquetas cíclicas está representada por una serie de estructuras repetitivas estacionarias del tipo que se muestra arriba. Diferentes cantidades de espacio horizontal entre estas estructuras sirven para diferenciar los símbolos 1 de los símbolos 0. Estos símbolos representan la palabra en la que está funcionando el sistema de etiquetas cíclicas, y el primero de estos símbolos se destruye al considerar cada regla de producción. Cuando este símbolo principal es un 1, se agregan nuevos símbolos al final de la cadena; cuando es 0, no se agregan nuevos símbolos. El mecanismo para lograr esto se describe a continuación.
Desde la derecha se introducen una serie de estructuras que se mueven hacia la izquierda del tipo que se muestra arriba, separadas por diferentes cantidades de espacio horizontal. Se combinan grandes cantidades de estas estructuras con diferentes espaciamientos para representar 0 y 1 en las reglas de producción del sistema de etiquetas cíclicas. Debido a que las reglas de producción del sistema de etiquetas se conocen en el momento de la creación del programa y se repiten infinitamente, los patrones de 0 y 1 en la condición inicial se pueden representar mediante una cadena que se repite infinitamente. Cada regla de producción está separada de la siguiente por otra estructura conocida como separador de reglas (o separador de bloques ), que se mueve hacia la izquierda a la misma velocidad que la codificación de las reglas de producción.
Cuando un separador de reglas que se mueve hacia la izquierda encuentra un símbolo estacionario en la cadena de datos del sistema de etiquetas cíclicas, hace que el primer símbolo que encuentra se destruya. Sin embargo, su comportamiento posterior varía según si el símbolo codificado por la cadena era un 0 o un 1. Si es un 0, el separador de reglas cambia a una nueva estructura que bloquea la regla de producción entrante. Esta nueva estructura se destruye cuando encuentra el siguiente separador de reglas.
Si, por otra parte, el símbolo de la cadena era un 1, el separador de reglas cambia a una nueva estructura que admite la regla de producción entrante. Aunque la nueva estructura se destruye de nuevo cuando encuentra el siguiente separador de reglas, primero permite que una serie de estructuras pasen hacia la izquierda. A continuación, se hace que estas estructuras se añadan al final de la cadena de datos del sistema de etiquetas cíclicas. Esta transformación final se logra por medio de una serie de pulsos de reloj que se repiten infinitamente y se mueven hacia la derecha en el patrón de movimiento hacia la derecha que se muestra arriba. Los pulsos de reloj transforman los símbolos 1 entrantes que se mueven hacia la izquierda de una regla de producción en símbolos 1 estacionarios de la cadena de datos, y los símbolos 0 entrantes de una regla de producción en símbolos 0 estacionarios de la cadena de datos.
La figura de arriba es el diagrama esquemático de la reconstrucción de un sistema de etiquetas cíclicas en la Regla 110.
