Regla 110

La regla 110 ( Regla inglesa  110 ) es una de las variantes del autómata celular elemental , en la que la secuencia de transformación da como resultado una secuencia binaria 01101110, que es la representación binaria del número decimal 110. Todos los autómatas celulares elementales son una cinta infinita. de celdas colocadas secuencialmente que pueden tener solo dos estados (0 y 1) y, al mismo tiempo, el estado futuro de la celda depende de los valores actuales de tres celdas: ella misma y sus dos vecinos más cercanos.

Un autómata que opera según la regla 110 se caracteriza por un comportamiento al borde del caos y la estabilidad . El mismo comportamiento es inherente al juego " Vida ". Se ha demostrado que un autómata celular con la regla 110 es Turing-completo , es decir, cualquier procedimiento computacional puede implementarse con él. Quizás este sea el sistema completo de Turing más simple [1] .

Definición

En los autómatas celulares más simples , una matriz unidimensional de ceros y unos se transforma de acuerdo con un conjunto de reglas. El valor de la celda en el siguiente paso se forma en función del estado actual de esta celda y sus dos vecinas (izquierda y derecha). La regla 110 tiene el siguiente conjunto de transformaciones:

El nombre Regla 110 está determinado por el código Wolfram  : la secuencia binaria 01101110 cuando se convierte a decimal dará el número 110.

En símbolos de álgebra booleana , la regla se puede escribir [2] :

Opción de conversión matemática:

Historia

Stephen Wolfram consideró todas las variantes posibles del autómata celular más simple, que consta de tres celdas de cinta vecinas, cada una de las cuales puede tomar solo dos estados (1/0, lleno/vacío, vivo/muerto). En total, puede haber 8 opciones para el estado actual de tres celdas vecinas. Dado que cada una de estas opciones puede generar solo dos nuevos estados de la celda central, entonces el número total de los autómatas más simples es 256. Si para las 8 opciones del estado actual, el conjunto de estados finales se interpreta como un número decimal en código binario , luego obtendremos una comparación de este número decimal con instrucciones de transformación de conjuntos de un solo dígito para uno de los autómatas celulares más simples. Wolfram las llamó " Reglas " con el número correspondiente.

Al establecer una secuencia caótica como estado inicial, Wolfram agrupó los resultados de transformación resultantes de acuerdo con diferentes reglas en 4 clases:

1. Convergen a un estado de uno cero o uno.
2. convergen a un estado cíclico o estable.
3. Mantener un estado caótico e inestable.
4. Se forman ambas regiones con estados cíclicos o estables, así como estructuras que interactúan entre sí de manera compleja.

Prueba de universalidad

Wolfram preparó los resultados del estudio de los autómatas celulares para su publicación en el libro A New Kind of Science (publicado en 2002). Fue asistido en el estudio por Matthew Cook. Los rifles de asalto de cuarta clase despertaron un interés considerable en Wolfram. Entre ellas se encontraba la Regla 110, sobre la cual Wolfram sugirió en 1985 que es Turing-completo [1] , es decir, es posible realizar cálculos universales. Matthew Cook desarrolló una prueba de la conjetura de Wolfram, que Cook presentó en la conferencia del Instituto Santa Fe en 1998.

Dado que el trabajo de Cook se basó en gran medida en la investigación de Wolfram, pero se dedicó solo a una de las reglas consideradas, Wolfram no quería que la prueba se publicara antes del lanzamiento de su propio libro, dedicado a la consideración de todo el conjunto de tales autómatas celulares. . Esto condujo a una demanda por violación de un acuerdo de no divulgación de la información obtenida mientras trabajaba en el libro [3] . Aunque la prueba presentada en la conferencia no se incluyó en la versión en papel de las actas de la conferencia, sin embargo, se conoció su existencia. En 2004, la prueba de Cook se publicó en la revista de Wolfram "Complex Systems" (número 15, volumen 1) [1] .

Para probar la universalidad de la Regla 110, Cook demostró que permite simular otro modelo computacional: el sistema de etiquetas cíclicas ., que es universal.

Primero, seleccionó tres estructuras de plantilla autorreproductivas. En las figuras, el tiempo va de arriba hacia abajo: la línea superior representa el estado inicial y cada línea subsiguiente representa el estado en la siguiente iteración. La estructura más a la izquierda en la figura desplaza dos celdas a la derecha y se repite cada tres generaciones, formando un camino diagonal de izquierda a derecha a través del patrón de fondo.

La estructura representada en el centro de la figura se desplaza ocho celdas hacia la izquierda y se repite cada treinta generaciones, formando una estructura diagonal de derecha a izquierda sobre el mismo patrón de fondo.

La estructura más a la derecha de la figura repite los estados anteriores sin desplazamientos cada siete generaciones y permanece inmóvil sobre el fondo base.

Cook luego ideó una forma de interacción de las combinaciones de estas estructuras para que el resultado pudiera interpretarse como un cálculo.

Notas

1. ↑ 1 2 3 Cook, Mateo (2004). “Universalidad en Autómatas Celulares Elementales” (PDF) . sistemas complejos . 15 :1-40. Archivado (PDF) desde el original el 28 de mayo de 2016 . Consultado el 10-02-2021 . Parámetro obsoleto utilizado |deadlink=( ayuda )
2. ↑ regla 110 - Wolfram|Alpha . Consultado el 10 de febrero de 2021. Archivado desde el original el 29 de enero de 2021. (indefinido)
3. ↑ Giles, Jim (2002). “¿Qué clase de ciencia es esta?”. naturaleza _ 417 (6886): 216-218. Código Bib : 2002Natur.417..216G . DOI : 10.1038/417216a . IDPM  12015565 .