Usuario:Carlos Rivas Solis/Regla 110

 

El autómata celular Regla 110 (a menudo llamado simplemente Regla 110 )​ es un autómata celular elemental con un comportamiento interesante 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 se reconoce como un sistema Turing completo. Esto implica que, en principio, con este autómata se podría simular cualquier cálculo o programa informático.

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

Definición

En un autómata celular elemental, un patrón unidimensional compuesto de 0 y 1 evoluciona de acuerdo a un conjunto simple de reglas. Para que un punto del patrón sea 0 o 1 en la nueva generación, depende de su valor actual, así como la de los de sus dos vecinos.

Una animación que representa la forma en que las reglas de un autómata celular unidimensional determinan la próxima generación, haciendo uso de la Regla 110.

El autómata celular Regla 110 posee el siguiente conjunto de reglas:

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

El nombre "Regla 110" deriva del hecho de que esta regla se puede resumir con la secuencia binaria 01101110 representado como un número binario; esto convertido a un valor decimal sería 110. Este es el esquema de nomenclatura que se usa en el código Wolfram.

Historia

En 2004, Matthew Cook publicó una prueba de que la Regla 110 con ciertos patrónes de fondos repetitivos particulares, se vuelve un sistemaTuring completo, es decir, capaz de realizar cálculo universal, algo que Stephen Wolfram había deducido en 1985. Cook presentó su prueba en la conferencia CA98 del Instituto Santa Fe antes que la publicación del libro de Wolfram Un nuevo tipo de ciencia. Esto resultó en un caso 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.

Propiedades interesantes

Entre los 88 autómatas celulares elementales únicos posibles, la Regla 110 ah sido la única a la que se ha demostrado la integridad de Turing, a pesar de que las pruebas de varias reglas similares siguen como simples derivaciones (por ejemplo, la Regla 124, que es el reflejo horizontal de la Regla 110). La regla 110 es posiblemente el sistema Turing completo más simple conocido.

La Regla 110, al igual que el Juego de la Vida, exhibe el comportamiento al que Wolfram llama "Clase 4", que no es completamente estable ni completamente caótico. Las estructuras localizadas aparecen e interactúan de maneras complejas.

Matthew Cook demostró que la Regla 110 es capaz de soportar el cómputo universal, emulando sucesivamente sistemas de etiquetas cíclicas, luego sistemas de 2 etiquetas y por último 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 en 2006 presentaron una construcción diferente que reemplazaba los sistemas de 2 etiquetas con máquinas de Turing en sentido de las agujas del reloj, teniendo una sobrecarga polinómica.

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 que la publicación de Un nuevo tipo de ciencia. Wolfram Research afirmó que esta presentación representaba una violación al acuerdo de confidencialidad de Cook con su empleador, obteniendo una orden judicial que excluía el artículo de Cook de las actas publicadas de la conferencia. Sin embargo, se dio a conocer la existencia de la prueba de Cook. El interés en su demostración no surgió tanto de sus resultados como de sus métodos, sino más bien de los detalles técnicos de su construcción.​ El carácter de la prueba de Cook difiere considerablemente del análisis de la regla 110 en A New Kind of Science. Desde entonces, Cook ha escrito un artículo exponiendo su prueba completa.

Cook demostró que la Regla 110 era universal (o Turing completo) al demostrar que era posible usar la regla para emular otro modelo computacional, el sistema de etiquetas cíclicas, que también se sabe que es universal. Primero aisló una serie de naves espaciales, una serie patrones localizados que se perpetúan a sí mismos, que podrían construirse según un patrón que se repite infinitamente en un universo de la Regla 110. Luego ideó una forma de 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 de la Regla 110. Estos se muestran en la imagen a continuación, rodeados por el patrón de fondo repetido. La estructura más a la izquierda se desplaza dos celdas hacia la derecha y se repite cada tres generaciones. Esto comprende la secuencia 0001110111 rodeada por el patrón de fondo indicado anteriormente, así como dos evoluciones diferentes de esta secuencia.

En las figuras, el tiempo transcurre de arriba hacia a abajo: la línea superior representa el estado inicial y cada línea siguiente ese mismo estado en el siguiente momento temporal.

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 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 pasando entre sí sin interactuar más que por una traslación (izquierda) e interactuando entre ellas para formar la tercera estructura (derecha).

Existen muchas naves espaciales en la Regla 110, pero estas no ocupan un lugar tan destacado en la prueba de universalidad como las nombradas anteriormente.

Construyendo el sistema de etiquetas cíclicas

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

• Una cadena de datos que es estacionaria;
• Una serie infinitamente repetida de reglas de producción finitas que comienzan por la derecha y se mueven hacia la izquierda;
• Una serie infinitamente repetida de pulsos de reloj que comienzan en 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 etiquetas cíclicas, las condiciones iniciales del autómata deben seleccionarse cuidadosamente para 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. Variando el espacio horizontal entre estas estructuras sirve para diferenciar los símbolos 1 de los símbolos 0. Estos símbolos representan la palabra en la que opera el sistema de etiquetas cíclicas, y el primer símbolo de este tipo se destruye al considerar cada regla 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 lograrlo 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 un espacio horizontal variable. Un gran número de estas estructuras se combinan con diferentes espacios para representar ceros y unos 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 ceros y unos en la condición inicial pueden representarse 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 hacia la izquierda encuentra un símbolo estacionario en la cadena de datos del sistema de etiquetas cíclicas, provocando que el primer símbolo que encuentre sea destruido. 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 es 0, el separador de reglas cambia a una nueva estructura que bloquea la regla de producción entrante. Esta nueva estructura es destruida cuando se encuentra con el siguiente separador de reglas.

Si, por el contrario, el símbolo en la cadena era un 1, el separador de reglas cambia a una nueva estructura la cual admite la regla de producción entrante. a pesar de que 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 a traves de la estructura. Luego 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 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.

Ver también

• Regla 30
• Regla 90
• Regla 184

 

 

Enlaces externos

• Wikimedia Commons alberga una categoría multimedia sobre Carlos Rivas Solis/Regla 110.

• 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 Regla 110 de 4 bits

[[Categoría:Modelos computacionales]] [[Categoría:Wolfram Research]] [[Categoría:Reglas de Wolfram]]