Hispanopedia Wiki
Articulo de referencia

Regla 110

Ejemplo de ejecución del autómata celular de regla 110 durante 256 iteraciones, comenzando desde una sola celda. El autómata celular de la Regla 110 (a menudo llamado simplement...

Hispanopedia WikiContenido en espanolLectura gratuita
Ejemplo de ejecución del autómata celular de regla 110 durante 256 iteraciones, comenzando desde una sola celda.

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 completa . [ 2 ] Esto implica que, en principio, cualquier cálculo o programa informático puede simularse utilizando este autómata.

Definición

En un autómata celular elemental, un patrón unidimensional de 0s y 1s 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.

Una animación de cómo las reglas de un autómata celular 1D determinan la siguiente generación, utilizando la Regla 110.

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 nomenclatura de códigos de Wolfram .

Historia

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 , lo cual 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 , A New Kind of Science . Esto dio lugar a 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 ]

Propiedades interesantes

Entre los 88 posibles autómatas celulares elementales únicos , la Regla 110 es la única para la que se ha demostrado directamente su completitud de Turing, aunque las demostraciones de varias reglas similares se derivan como corolarios simples (por ejemplo, la Regla 124, que es la reflexión horizontal de la Regla 110). La Regla 110 ha sido descrita como uno de los sistemas Turing completos más simples conocidos. [ 2 ] [ 5 ] [ 6 ]

La regla 110, al igual que el Juego de la Vida , exhibe lo que Wolfram denomina " comportamiento de Clase 4 ", que no es ni completamente estable ni completamente caótico. Aparecen estructuras localizadas que interactúan de maneras complejas. [ 7 ]

Matthew Cook demostró que la Regla 110 es capaz de soportar la computación universal emulando sucesivamente sistemas de etiquetas cíclicas , luego sistemas de 2 etiquetas y, finalmente, 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 sentido horario y tiene una sobrecarga polinómica . [ 6 ]

La prueba de 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 alegó que esta presentación violaba el acuerdo de confidencialidad de Cook con su empleador y obtuvo una orden judicial que excluía el trabajo de Cook de las actas publicadas de la conferencia. Sin embargo, la existencia de la prueba de Cook se dio a conocer. El interés en su prueba no radicaba tanto en su resultado como en sus métodos, específicamente en 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 A New Kind of Science . Desde entonces, Cook ha escrito un artículo donde expone su prueba completa. [ 2 ]

Cook demostró que la Regla 110 era universal (o Turing completa) al mostrar que era posible usarla para emular otro modelo computacional, el sistema de etiquetas cíclicas , que se sabe que es universal. Primero aisló varias naves espaciales , patrones localizados que se autoperpetúan, que podían construirse sobre un patrón que se repetía infinitamente en un universo regido por 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 un número finito de patrones localizados se incrusten 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, tres patrones localizados revisten especial importancia. Se muestran en la imagen inferior, rodeados por el patrón de fondo repetitivo. La estructura situada más a la izquierda se desplaza dos celdas a la derecha y se repite cada tres generaciones. Comprende la secuencia 0001110111, rodeada por el patrón de fondo mencionado anteriormente, así como dos evoluciones diferentes de esta secuencia.

En las figuras, el tiempo transcurre de arriba abajo: la línea superior representa el estado inicial y cada línea siguiente el estado en el siguiente instante.

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

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

A continuación se muestra una imagen que ilustra cómo las dos primeras estructuras se atraviesan entre sí sin interactuar más que por traslación (izquierda), y cómo interactúan para formar la tercera estructura (derecha).

En la Regla 110 aparecen muchas otras naves espaciales, pero no ocupan un lugar tan destacado en la prueba de universalidad.

Construcción del sistema de etiquetas cíclicas

El sistema de etiquetado cíclico consta de tres componentes principales:

  • Una cadena de datos que es estacionaria;
  • Una serie infinitamente repetitiva de reglas de producción finitas que comienzan por la derecha y se mueven hacia la izquierda;
  • Una serie de pulsos de reloj que se repiten infinitamente, comenzando por la izquierda y avanzando hacia la derecha.

El espaciado inicial entre estos componentes es de suma importancia. Para que el autómata celular implemente el sistema de etiquetas cíclicas, sus condiciones iniciales deben seleccionarse cuidadosamente para que las diversas estructuras localizadas que contiene interactúen de forma altamente ordenada.

La cadena de datos en el sistema de etiquetas cíclicas se representa mediante una serie de estructuras repetitivas estacionarias del tipo mostrado anteriormente. El espacio horizontal variable entre estas estructuras sirve para diferenciar los símbolos 1 de los símbolos 0. Estos símbolos representan la palabra sobre la que opera el sistema de etiquetas cíclicas, y el primero de estos símbolos se elimina al considerar cada regla de producción. Cuando este símbolo inicial es un 1, se añaden nuevos símbolos al final de la cadena; cuando es un 0, no se añaden nuevos símbolos. El mecanismo para lograr esto se describe a continuación.

Desde la derecha se introduce una serie de estructuras que se mueven hacia la izquierda, del tipo mostrado anteriormente, separadas por diferentes cantidades de espacio horizontal. Un gran número de estas estructuras se combinan con distintos espaciados para representar 0s y 1s en las reglas de producción del sistema de etiquetas cíclicas. Dado 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 0s y 1s 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 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 fijo en la cadena de datos del sistema de etiquetas cíclicas, destruye el primer símbolo que encuentra. Sin embargo, su comportamiento posterior varía según si el símbolo codificado en la cadena era un 0 o un 1. Si era un 0, el separador de reglas se transforma en una nueva estructura que bloquea la regla de producción entrante. Esta nueva estructura se destruye al encontrar el siguiente separador de reglas.

Si, por otro lado, el símbolo en la cadena es un 1, el separador de reglas se transforma en una nueva estructura que admite la regla de producción entrante. Aunque la nueva estructura se destruye nuevamente al encontrar el siguiente separador de reglas, primero permite que una serie de estructuras pasen hacia la izquierda. 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, siguiendo el patrón mostrado anteriormente. Los pulsos de reloj transforman los símbolos 1 entrantes que se mueven hacia la izquierda, provenientes de una regla de producción, en símbolos 1 estacionarios de la cadena de datos, y los símbolos 0 entrantes, provenientes de una regla de producción, en símbolos 0 estacionarios de la cadena de datos.

Sistema de etiquetas cíclicas en funcionamiento

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

Véase también

Notas

  1. ↑ 110 es el número 110 , escrito en notación decimal convencional, y por lo tanto se pronuncia como se pronuncian los números nominales normalmente. Por ejemplo, Stephen Wolfram pronuncia el nombre "regla uno-diez". [ 1 ]

Referencias

  1. ↑ Stephen Wolfram (2003). Un nuevo tipo de ciencia - Stephen Wolfram . Televisión de la Universidad de California (UCTV). El evento ocurre a las 9:51 . Recuperado el 19 de junio de 2023 .
  2. 1 2 3 4 Cook (2004) .
  3. ↑ Wolfram Research Inc. contra Cook (2:00-cv-09357) (a veces citado como "Wolfram Research Inc. contra Matthew Cook. 8/31 CV00-9357 CBM")
  4. ↑ Giles (2002) .
  5. ↑ Wolfram (2002) , págs. 169, 675–691 
  6. 1 2 Neary y Woods (2006) .
  7. ↑ Wolfram (2002) , pág. 229 
  8. ↑ Martínez, Genaro J.; Seck Tuoh Mora, Juan; Chapa, Sergio; Lemaitre, Christian (abril de 2019). "Breves notas e historia de la computación en México durante 50 años" . International Journal of Parallel, Emergent and Distributed Systems . 35 (2): 185– 192. arXiv : 1905.07527 . doi : 10.1080/17445760.2019.1608990 . S2CID 150262966. Recuperado el 15 de abril de 2020 . 

Obras citadas

  • Cook, Matthew (2004). "Universalidad en autómatas celulares elementales" (PDF) . Sistemas complejos . 15 : 1–40 . doi : 10.25088/ComplexSystems.15.1.1 .
  • Giles, Jim (2002). "¿Qué clase de ciencia es esta?" . Nature . 417 (6886): 216– 218. Bibcode : 2002Natur.417..216G . doi : 10.1038/417216a . PMID 12015565 . S2CID 10636328 .  
  • Neary, Turlough; Woods, Damien (2006). "P-completitud de la regla 110 del autómata celular". 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. Lecture Notes in Computer Science. Vol.  4051. Springer. pp. 132–143 . doi : 10.1007/11786986_13 . ISBN  978-3-540-35904-3.
  • Wolfram, Stephen (2002). Un nuevo tipo de ciencia . Wolfram Media. ISBN 1-57955-008-8.

Lecturas adicionales

  • 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 . Actas electrónicas en informática teórica. Vol.  1. págs. 31–55 . arXiv : 0906.3248v1 . doi : 10.4204/EPTCS.1.4 . S2CID 10266058 .  
  • Martínez, Genaro J.; Adamatzky, A.; Chen, Fangyue; Chua, Leon (2012). "Sobre colisiones de solitones 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 . S2CID 10165042 . 
  • Martínez, Genaro J.; Adamatzky, A.; Stephens, Christopher R.; Hoeflich, Alejandro F. (2011). "Supercolisionadores de autómatas celulares" . Int. J. Mod. Phys. C. 22 ( 4): 419– 439. arXiv : 1105.4332 . Bibcode : 2011IJMPC..22..419M . doi : 10.1142/S0129183111016348 . S2CID 7508070 . 
  • Martínez, Genaro J.; McIntosh, Harold V .; Mora, Juan CST; Vergara, Sergio VC (2003–2008). «Reproducción de los sistemas de etiquetas cíclicas desarrollados por Matthew Cook con la 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". Journal of Cellular Automata . 3 (3): 231– 270. arXiv : 0706.3348v1 . Bibcode : 2007arXiv0706.3348J .
  • Martínez, Genaro J.; McIntosh, Harold V .; Mora, Juan CST; Vergara, Sergio VC (2007). «Regla 110 objetos 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). "Gliders in Rule 110" (PDF) . International Journal of Unconventional Computing . 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) . Avances en vida artificial . Notas de clase en ciencias de la computación. Vol.  2801. pp. 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 del éter en la regla 110" .
  • McIntosh, Harold V. (1999). "Regla 110 en lo que respecta a la presencia de planeadores" (PDF) .
  • McIntosh, Harold V. (2002). "¡La regla 110 es universal!" (PDF) .
  • Regla 110 — de Wolfram MathWorld
  • Regla 110 del atlas de autómatas celulares de Wolfram
  • Repositorio de la Regla 110
  • Implementación mecánica basada en mármol de una computadora de 4 bits con regla 110.