Autómata celular elemental

Un autómata celular elemental  es un autómata celular con un arreglo unidimensional de celdas en forma de cinta sin fin por ambos lados, que tiene dos posibles estados de celda (0 y 1, "muerto" y "vivo", "vacío" y "lleno") y una regla para determinar el estado de la celda en el siguiente paso, usando solo el estado de la celda y sus dos vecinos en el paso actual. En general, tales autómatas se encuentran entre los autómatas celulares más simples posibles, sin embargo, bajo ciertas reglas, muestran un comportamiento complejo; por lo tanto, usar la regla 110 conduce a un autómata completo de Turing .

Código Wolframio

En total, existen combinaciones posibles del estado de la celda y los estados de sus dos vecinos. La regla que define el autómata celular elemental debe indicar el siguiente estado (0 o 1) para cada uno de estos posibles casos, por lo que el número total de reglas . Stephen Wolfram propuso un esquema de numeración para estas reglas, conocido como el código Wolfram , que asigna a cada regla un número entre 1 y 255. Este sistema fue publicado por primera vez por Wolfram en un artículo de 1983 [1] y luego se usó en su libro A New Kind of Science ” ( Ing. Ciencia de un nuevo tipo ). [2]  

Para obtener el código Wolfram, debe anotar las configuraciones posibles (111, 110, ..., 001, 000) en orden descendente, escribir los estados correspondientes debajo de ellos e interpretar la secuencia resultante de ceros y unos como un número en el sistema numérico binario . Por ejemplo, el siguiente esquema da como resultado el código correspondiente a la regla 110 :

Reflexiones y adiciones

Algunas de las 256 reglas son trivialmente equivalentes entre sí debido a la presencia de dos tipos de transformaciones. La primera es una reflexión sobre el eje vertical, en la que se intercambian los vecinos izquierdo y derecho y se obtiene una regla reflejada .  Por ejemplo, la regla 110 se convierte en la regla 118:

Entre las 256 reglas, hay 64 con simetría especular ( ing.  amphichiral ).

El segundo tipo de transformación es la sustitución de los roles 0 y 1 en la definición, lo que da una regla adicional ( regla complementaria inglesa  ). Por ejemplo, la regla 118 se convierte en la regla 137:

Solo 16 reglas de 256 coinciden con sus adiciones. Hasta este par de transformaciones (incluidas las aplicadas simultáneamente, el orden no es importante), hay 88 autómatas celulares elementales no equivalentes. [3]

Métodos de investigación

La configuración más simple

Uno de los métodos para estudiar los autómatas celulares elementales es considerar la evolución de la configuración inicial más simple, es decir, que consta de una sola célula viva (que contiene 1). Si la regla tiene un código Wolfram par, entonces no hay generación espontánea de vida (la combinación 000 no da 1 en el medio en la próxima generación), y por lo tanto cada estado de la configuración más simple tiene un número finito de no cero. celdas y puede interpretarse como un número en notación binaria.[ ¿cómo? ] La secuencia de estos números define una función generadora , que es racional , es decir, la razón de dos polinomios , y a menudo tiene una forma relativamente simple.

Configuraciones aleatorias

También es útil considerar la evolución de las configuraciones iniciales aleatorias. Para ello, existe una división en las siguientes clases informales de autómatas celulares , inventadas por Wolfram: [4]

• Clase 1: Converge rápidamente a un estado de todos ceros o unos. Wolfram cita como ejemplos las reglas 0, 32, 160, 232.
• Clase 2: Convergiendo rápidamente a un estado cíclico o estable . Por ejemplo, reglas 4, 108, 218, 250.
• Clase 3: Almacenado en un estado aleatorio. Por ejemplo, las reglas 22, 30 , 126, 150, 182.
• Clase 4: Se forman ambas regiones con estados cíclicos o estables, así como estructuras que interactúan entre sí de manera compleja. Un ejemplo es la regla 110 , que es Turing completa .