Regla 110

El autómata celular de la Regla 110 (a menudo llamado simplemente Regla 110 ) 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 . Como la vida, se sabe que la Regla 110 es Turing completa . Esto implica que, en principio, con este autómata se puede simular cualquier cálculo o programa informático.

Un ejemplo de ejecución de un autómata celular de la regla 110

Definición

En un autómata celular elemental, un patrón unidimensional de 0 y 1 evoluciona de acuerdo con un conjunto simple de reglas. El 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.

Una animación de la forma en que las reglas de un autómata celular 1D determinan la próxima generación, utilizando la Regla 110.

El autómata Rule 110 tiene el siguiente conjunto de reglas:

Patrón actual	111	110	101	100	011	010	001	000
Nuevo estado para celda central	0	1	1	0	1	1	1	0

El nombre "Regla 110" deriva del hecho de que esta regla se puede resumir en la secuencia binaria 01101110; interpretado como un número binario , corresponde al valor decimal 110.

Historia

En 2004, Matthew Cook publicó una prueba de que la Regla 110 es Turing completo , es decir, capaz de computación universal , que Stephen Wolfram había conjeturado en 1985. ^[1] Cook presentó su prueba en la conferencia del Instituto Santa Fe CA98 antes de la publicación del libro A de Wolfram. Nuevo tipo de ciencia . Esto resultó en un asunto legal basado en un acuerdo de confidencialidad con Wolfram Research . Wolfram Research bloqueó la publicación de la prueba de Cook durante varios años. ^[2]

Propiedades interesantes

Entre los 88 posibles autómatas celulares elementales únicos , la Regla 110 es la única para la que se ha probado la integridad de Turing, aunque las pruebas de varias reglas similares deben seguir como simples corolarios (por ejemplo, la Regla 124, que es el reflejo horizontal de la Regla 110). La regla 110 es posiblemente el sistema completo de Turing más simple que se conoce. ^{[1] [3]}

La regla 110, como el Juego de la vida , exhibe lo que Wolfram llama " comportamiento de Clase 4 ", que no es ni completamente estable ni completamente caótico. Las estructuras localizadas aparecen e interactúan de formas complejas. ^[4]

Matthew Cook demostró que la Regla 110 es capaz de soportar la computación universal emulando sucesivamente los sistemas de etiquetas cíclicas , luego el sistema de 2 etiquetas y luego las 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 . ^[5]

La prueba de la universalidad

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 A New Kind of Science . Wolfram Research afirmó que esta presentación violó el acuerdo de no divulgación de Cook con su empleador y obtuvo una orden judicial que excluía el artículo de Cook de las actas de la conferencia publicadas. No obstante, se conoció la existencia de la prueba de Cook. El interés por su prueba no se deriva tanto de su resultado como de sus métodos, específicamente de los detalles técnicos de su construcción. ^[6] El carácter de la demostración de Cook difiere considerablemente de la discusión de la Regla 110 en A New Kind of Science . Desde entonces, Cook ha escrito un artículo en el que presenta su prueba completa. ^[1]

Cook demostró que la Regla 110 era universal (o Turing completa) al demostrar que era posible usar la regla para emular otro modelo computacional, el sistema cíclico de etiquetas , que se sabe que es universal. Primero aisló una serie de naves espaciales , patrones localizados que se perpetúan a sí mismos, que podrían construirse en un patrón infinitamente repetido en un universo de la Regla 110. Luego ideó una forma para que las combinaciones de estas estructuras interactuaran de una manera que pudiera aprovecharse para la computación.

Naves espaciales en la Regla 110

La función de la máquina universal en la Regla 110 requiere que se incruste un número finito 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 .

Tres patrones localizados son de particular importancia en la máquina universal Rule 110. Se muestran en la imagen de abajo, rodeados por el patrón de fondo repetido. La estructura más a la izquierda se desplaza hacia las dos células de la derecha y se repite cada tres generaciones. Comprende la secuencia 0001110111 rodeada por el patrón de fondo dado anteriormente, 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 de la próxima vez.

La estructura central se desplaza a la izquierda de ocho celdas y se repite cada treinta generaciones. Comprende la secuencia 1001111 rodeada por el patrón de fondo dado anteriormente, así como veintinueve evoluciones diferentes de esta secuencia.

La estructura más a la derecha permanece estacionaria y se repite cada siete generaciones. Comprende la secuencia 111 rodeada por el patrón de fondo dado anteriormente, así como cinco evoluciones diferentes de esta secuencia.

A continuación se muestra una imagen que muestra las dos primeras estructuras que se atraviesan entre sí sin interactuar más que por traducción (izquierda) e interactuando para formar la tercera estructura (derecha).

Hay muchas otras naves espaciales en la Regla 110, pero no aparecen de manera tan prominente en la prueba de universalidad.

Construyendo el sistema cíclico de etiquetas

La maquinaria del sistema de etiquetas cíclicas tiene tres componentes principales:

• Una cadena de datos estacionaria;
• Una serie infinitamente repetida de reglas de producción finitas que comienzan a la derecha y se mueven hacia la izquierda;
• Una serie de pulsos de reloj que se repiten infinitamente y que comienzan a la izquierda y se mueven hacia la derecha.

El espacio inicial entre estos componentes es de suma importancia. Para que el autómata celular implemente el sistema de etiqueta cíclica, las condiciones iniciales del autómata deben seleccionarse cuidadosamente de modo que las diversas estructuras localizadas contenidas en él interactúen de una manera altamente ordenada.

La cadena de datos en el sistema de etiquetas cíclicas está representada por una serie de estructuras repetidas estacionarias del tipo que se muestra arriba. Las cantidades variables de espacio horizontal entre estas estructuras sirven para diferenciar 1 símbolo de 0 símbolos. Estos símbolos representan la palabra en la que está funcionando el sistema de etiquetas cíclicas, y el primer símbolo de este tipo se destruye al considerar todas las reglas de producción. Cuando este símbolo inicial 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.

Entrando por la derecha hay una serie de estructuras que se mueven hacia la izquierda del tipo que se muestra arriba, separadas por cantidades variables de espacio horizontal. Un gran número de estas estructuras se combinan 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 al mismo ritmo que la codificación de las reglas de producción.

Cuando un separador de reglas que se mueve a la izquierda encuentra un símbolo estacionario en la cadena de datos del sistema de etiquetas cíclicas, hace que se destruya el primer símbolo que encuentra. Sin embargo, su comportamiento posterior varía dependiendo de si el símbolo codificado por la cadena había sido un 0 o un 1. Si 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 otro lado, el símbolo en 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 nuevamente cuando se encuentra con el siguiente separador de reglas, primero permite que una serie de estructuras pasen hacia la izquierda. Luego, estas estructuras se añaden al final de la cadena de datos del sistema de etiquetas cíclicas. Esta transformación final se logra mediante 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.

Funcionamiento del sistema de etiquetas cíclicas

La figura anterior es el diagrama esquemático de la reconstrucción de un sistema de etiquetas cíclicas en la Regla 110.

Ver también

• Regla 30
• Regla 90
• Regla 184

Referencias

1. Cook (2004) .
2. Giles (2002) .
3. Wolfram 2002 , págs. 169, 675–691
4. Wolfram 2002 , p. 229
5. Neary y Woods (2006) .
6. Martínez, Genaro J .; Seck Tuoh Mora, Juan; Chapa, Sergio; Lemaitre, Christian (abril de 2019). "Breves apuntes e historia de la computación en México durante 50 años" . Revista Internacional de Sistemas Paralelos, Emergentes y Distribuidos . 35 : 1–8. arXiv : 1905.07527 . doi : 10.1080 / 17445760.2019.1608990 . Consultado el 15 de abril de 2020 .

Trabajos citados

• Cook, Matthew (2004). "Universalidad en autómatas celulares elementales" (PDF) . Sistemas complejos . 15 : 1–40.
• Giles, Jim (2002). "¿Qué tipo de ciencia es esta?". Naturaleza . 417 (6886): 216–218. Código Bibliográfico : 2002Natur.417..216G . doi : 10.1038 / 417216a . PMID  12015565 .
• Neary, Turlough; Woods, Damien (2006). "P-completitud del autómata celular Regla 110". En Bugliesi, Michele; Preneel, Bart; Sassone, Vladimiro; Wegener, Ingo (eds.). Autómatas, Lenguajes y programación: 33º Coloquio Internacional, ICALP 2006, Venecia, Italia, 10-14 de julio de 2006, Actas, Parte I . Apuntes de conferencias en informática. 4051 . Saltador. págs. 132-143. doi : 10.1007 / 11786986_13 .
• Wolfram, Stephen (2002). Un nuevo tipo de ciencia . Wolfram Media. ISBN 1-57955-008-8.

Otras lecturas

• Cook, Matthew (2008). "Una visión concreta del cálculo de la regla 110". En Neary, T .; Woods, D .; Seda, AK; Murphy, N. (eds.). La complejidad de los programas simples . Procedimientos electrónicos en informática teórica . 1 . págs. 31–55. arXiv : 0906.3248v1 . doi : 10.4204 / EPTCS.1.4 .
• Martínez, Genaro J .; Adamatzky, A .; Chen, Fangyue; Chua, León (2012). "Sobre colisiones de solitón entre localizaciones en autómatas celulares elementales complejos: reglas 54 y 110 y más allá". Sistemas complejos . 21 (2): 117-142. arXiv : 1301.6258 . doi : 10.25088 / ComplexSystems.21.2.117 .
• Martínez, Genaro J .; Adamatzky, A .; Stephens, Christopher R .; Hoeflich, Alejandro F. (2011). "Supercolisionadores de autómatas celulares" . En t. J. Mod. Phys. C . 22 (4): 419–439. arXiv : 1105.4332 . Código bibliográfico : 2011IJMPC..22..419M . doi : 10.1142 / S0129183111016348 .
• Martínez, Genaro J .; McIntosh, Harold V .; Mora, Juan CST; Vergara, Sergio VC (2003-2008). "Reproducción de los sistemas cíclicos de etiquetas desarrollados por Matthew Cook con Regla 110 utilizando las fases fi_1" (PDF) . Revista de autómatas celulares . 6 (2-3): 121-161.
• Martínez, Genaro J .; McIntosh, Harold V .; Mora, Juan CST; Vergara, Sergio VC (2008). "Determinación de un lenguaje regular mediante estructuras basadas en planeadores llamadas fases fi_1 en la Regla 110". Revista de autómatas celulares . 3 (3): 231–270. arXiv : 0706.3348v1 . Código Bibliográfico : 2007arXiv0706.3348J .
• Martínez, Genaro J .; McIntosh, Harold V .; Mora, Juan CST; Vergara, Sergio VC (2007). "Objetos de la regla 110 y otras construcciones basadas en colisiones" (PDF) . Revista de autómatas celulares . 2 (3): 219–242.
• Martínez, Genaro J .; McIntosh, Harold V .; Mora, Juan CST (2006). "Planeadores en la Regla 110" (PDF) . En t. J. De la informática no convencional . 2 : 1-49.
• Martínez, Genaro J .; McIntosh, Harold V .; Mora, Juan CST (2003). "Producción de planeadores por colisiones en la Regla 110" (PDF) . Apuntes de conferencias en informática . 2801 : 175-182. doi : 10.1007 / 978-3-540-39432-7_19 . ISBN 978-3-540-20057-4.
• Martínez, Genaro J .; McIntosh, Harold V. (2001). "ATLAS: Colisiones de planeadores como fases de éter en la regla 110" .
• McIntosh, Harold V. (1999). "Regla 110 en lo que se refiere a la presencia de planeadores" (PDF) .
• McIntosh, Harold V. (2002). "¡La regla 110 es universal!" (PDF) .

enlaces externos

• Regla 110 - de Wolfram MathWorld
• Regla 110 en el atlas de autómatas celulares de Wolfram
• Repositorio de la regla 110
• Implementación mecánica basada en mármol de una computadora Rule 110 de 4 bits