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 . Al igual que en la vida, se sabe que la Regla 110 con un patrón de fondo particular que se repite es Turing completo . [1] Esto implica que, en principio, con este autómata se puede simular cualquier cálculo o programa informático.
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.
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.
En 2004, Matthew Cook publicó una prueba de que la Regla 110 con un patrón de fondo repetitivo particular 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 de Wolfram A New Kind of Science . 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]
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]
