Autómata celular

Un autómata celular (pl. autómatas celulares) es un modelo discreto de computación estudiado en la teoría de autómatas. Los autómatas celulares también se denominan espacios celulares, autómatas de teselado, estructuras homogéneas, estructuras celulares, estructuras de teselado y matrices iterativas. Los autómatas celulares han encontrado aplicación en varias áreas, incluida la física, la biología teórica y el modelado de microestructuras.

Un autómata celular consta de una cuadrícula regular de celdas, cada una en uno de un número finito de estados, como encendido y apagado (en contraste con una red de mapa acoplada). La cuadrícula puede tener cualquier número finito de dimensiones. Para cada celda, se define un conjunto de celdas denominado su vecindad en relación con la celda especificada. Se selecciona un estado inicial (tiempo t = 0) asignando un estado para cada celda. Se crea una nueva generación (avanzando t en 1), según alguna regla fija (generalmente, una función matemática)que determina el nuevo estado de cada celda en términos del estado actual de la celda y los estados de las celdas en su vecindad. Normalmente, la regla para actualizar el estado de las celdas es la misma para cada celda y no cambia con el tiempo, y se aplica a toda la red simultáneamente, aunque se conocen excepciones, como el autómata celular estocástico y el autómata celular asíncrono.

El concepto fue descubierto originalmente en la década de 1940 por Stanislaw Ulam y John von Neumann cuando eran contemporáneos en el Laboratorio Nacional de Los Álamos. Si bien algunos lo estudiaron durante las décadas de 1950 y 1960, no fue hasta la década de 1970 y el Juego de la vida de Conway, un autómata celular bidimensional, que el interés en el tema se expandió más allá de la academia. En la década de 1980, Stephen Wolfram se dedicó a un estudio sistemático de autómatas celulares unidimensionales, o lo que él llama autómatas celulares elementales; su asistente de investigación Matthew Cook demostró que una de estas reglas es Turing-completo.

Las clasificaciones principales de los autómatas celulares, tal como las describe Wolfram, están numeradas del uno al cuatro. Son, en orden, autómatas en los que los patrones generalmente se estabilizan en la homogeneidad, autómatas en los que los patrones evolucionan hacia estructuras en su mayoría estables u oscilantes, autómatas en los que los patrones evolucionan de una manera aparentemente caótica y autómatas en los que los patrones se vuelven extremadamente complejos y pueden durar varios años. mucho tiempo, con estructuras locales estables. Se cree que esta última clase es computacionalmente universal o capaz de simular una máquina de Turing. Los tipos especiales de autómatas celulares son reversibles, donde solo una única configuración conduce directamente a una posterior, y totalistas., en el que el valor futuro de las celdas individuales solo depende del valor total de un grupo de celdas vecinas. Los autómatas celulares pueden simular una variedad de sistemas del mundo real, incluidos los biológicos y químicos.

Visión general

Una forma de simular un autómata celular bidimensional es con una hoja infinita de papel cuadriculado junto con un conjunto de reglas que deben seguir las células. Cada cuadrado se denomina "celda" y cada celda tiene dos estados posibles, blanco y negro. La vecindad de una celda son las celdas cercanas, generalmente adyacentes. Los dos tipos más comunes de barrios son el barrio de von Neumann y el barrio de Moore. El primero, llamado así por el teórico fundador del autómata celular, consta de cuatro celdas adyacentes ortogonalmente. Este último incluye la vecindad de von Neumann, así como las cuatro celdas adyacentes en diagonal. Para tal celda y su vecindad de Moore, hay 512 (= 2) patrones posibles. Para cada uno de los 512 patrones posibles, la tabla de reglas indicaría si la celda central será blanca o negra en el siguiente intervalo de tiempo. Game of Life de Conway es una versión popular de este modelo. Otro tipo de vecindad común es la vecindad extendida de von Neumann, que incluye las dos celdas más cercanas en cada dirección ortogonal, para un total de ocho. La ecuación general para un sistema de reglas de este tipo es k, donde k es el número de estados posibles para una celda y s es el número de celdas vecinas (incluida la celda que se va a calcular) que se utiliza para determinar el siguiente estado de la celda.Así, en el sistema bidimensional con vecindad de Moore, el número total de autómatas posibles sería 2, o1,34 × 10.

Por lo general, se supone que todas las células del universo comienzan en el mismo estado, a excepción de un número finito de células en otros estados; la asignación de valores de estado se denomina configuración. De manera más general, a veces se supone que el universo comienza cubierto con un patrón periódico, y solo un número finito de células viola ese patrón. La última suposición es común en autómatas celulares unidimensionales.

Los autómatas celulares a menudo se simulan en una cuadrícula finita en lugar de infinita. En dos dimensiones, el universo sería un rectángulo en lugar de un plano infinito. El problema obvio con las cuadrículas finitas es cómo manejar las celdas en los bordes. La forma en que se manejen afectará los valores de todas las celdas de la cuadrícula. Un método posible es permitir que los valores en esas celdas permanezcan constantes. Otro método es definir los vecindarios de manera diferente para estas celdas. Se podría decir que tienen menos vecinos, pero entonces también habría que definir nuevas reglas para las celdas ubicadas en los bordes. Estas celdas generalmente se manejan con un toroidaldisposición: cuando uno sale por la parte superior, uno entra en la posición correspondiente en la parte inferior, y cuando uno sale por la izquierda, uno entra por la derecha. (Esencialmente, esto simula un mosaico periódico infinito y, en el campo de las ecuaciones diferenciales parciales, a veces se denomina condiciones de contorno periódicas). y los bordes inferiores del tubo para formar un toro (forma de rosquilla). Los universos de otras dimensiones se manejan de manera similar. Esto resuelve problemas de límites con vecindades, pero otra ventaja es que es fácilmente programable usando funciones aritméticas modulares. Por ejemplo, en un autómata celular unidimensional como los ejemplos a continuación, la vecindad de una celda x_i es { x _{i −1}, x _i, x _{i +1} }, donde t es el paso de tiempo (vertical) e i es el índice (horizontal) en una generación.

Historia

Stanislaw Ulam, mientras trabajaba en el Laboratorio Nacional de Los Álamos en la década de 1940, estudió el crecimiento de los cristales utilizando una red reticular simple como modelo. Al mismo tiempo, John von Neumann, colega de Ulam en Los Álamos, estaba trabajando en el problema de los sistemas autorreplicantes. El diseño inicial de Von Neumann se basó en la idea de que un robot construye otro robot. Este diseño se conoce como el modelo cinemático. Mientras desarrollaba este diseño, von Neumann se dio cuenta de la gran dificultad de construir un robot autorreplicante y del gran costo de proporcionar al robot un "mar de piezas" a partir del cual construir su replicante. Neumann escribió un artículo titulado "La teoría general y lógica de los autómatas" para el Simposio Hixon en 1948.sistema discreto para crear un modelo reduccionista de autorreplicación. Nils Aall Barricelli realizó muchas de las primeras exploraciones de estos modelos de vida artificial.

Ulam y von Neumann crearon un método para calcular el movimiento de líquidos a fines de la década de 1950. El concepto impulsor del método era considerar un líquido como un grupo de unidades discretas y calcular el movimiento de cada una en función del comportamiento de sus vecinos. Así nació el primer sistema de autómatas celulares. Al igual que la red de celosía de Ulam, los autómatas celulares de von Neumann son bidimensionales, con su autorreplicador implementado algorítmicamente. El resultado fue una copiadora y constructora universal trabajando dentro de un autómata celular con un vecindario pequeño (solo aquellas celdas que se tocan son vecinas; para los autómatas celulares de von Neumann, solo celdas ortogonales) y con 29 estados por celda.Von Neumann dio una prueba de existencia de que un patrón particular haría infinitas copias de sí mismo dentro del universo celular dado al diseñar una configuración de 200,000 células que podría hacerlo. Este diseño se conoce como modelo de teselación y se denomina constructor universal de von Neumann.

También en la década de 1940, Norbert Wiener y Arturo Rosenblueth desarrollaron un modelo de medios excitables con algunas de las características de un autómata celular. Su motivación específica fue la descripción matemática de la conducción de impulsos en los sistemas cardíacos. Sin embargo, su modelo no es un autómata celular porque el medio en el que se propagan las señales es continuo y los frentes de onda son curvas. Un verdadero modelo de autómata celular de medios excitables fue desarrollado y estudiado por JM Greenberg y SP Hastings en 1978; ver Autómata celular de Greenberg-Hastings. El trabajo original de Wiener y Rosenblueth contiene muchas ideas y continúa siendo citado en publicaciones de investigación modernas sobre arritmia cardíaca y sistemas excitables.

En la década de 1960 se estudian los autómatas celulares como un tipo particular de sistema dinámico y se establece por primera vez la conexión con el campo matemático de la dinámica simbólica. En 1969, Gustav A. Hedlund compiló muchos resultados siguiendo este punto de vista en lo que todavía se considera un artículo seminal para el estudio matemático de los autómatas celulares. El resultado más fundamental es la caracterización en el teorema de Curtis-Hedlund-Lyndon del conjunto de reglas globales de autómatas celulares como el conjunto de endomorfismos continuos de espacios de desplazamiento.

En 1969, el pionero informático alemán Konrad Zuse publicó su libro Calculating Space, proponiendo que las leyes físicas del universo son discretas por naturaleza y que todo el universo es el resultado de un cálculo determinista en un único autómata celular; La "teoría de Zuse" se convirtió en la base del campo de estudio llamado física digital.

También en 1969, el científico informático Alvy Ray Smith completó una disertación de doctorado en Stanford sobre la teoría de los autómatas celulares, el primer tratamiento matemático de CA como una clase general de computadoras. De esta disertación surgieron muchos artículos: mostró la equivalencia de vecindarios de varias formas, cómo reducir un Moore a un vecindario de von Neumann o cómo reducir cualquier vecindario a un vecindario de von Neumann. Demostró que las CA bidimensionales son universales de computación, introdujo las CA unidimensionales y demostró que también son universales de computación, incluso con vecindades simples. Mostró cómo subsumir la prueba compleja de von Neumann de la universalidad de la construcción (y, por lo tanto, las máquinas que se reproducen a sí mismas) en una consecuencia de la universalidad de la computación en una CA unidimensional.Pensado como la introducción a la edición alemana del libro de von Neumann sobre CA, escribió una encuesta del campo con docenas de referencias a artículos de muchos autores en muchos países durante una década de trabajo, a menudo pasado por alto por los investigadores modernos de CA.

En la década de 1970, un autómata celular bidimensional de dos estados llamado Game of Life se hizo ampliamente conocido, particularmente entre la comunidad informática temprana. Inventado por John Conway y popularizado por Martin Gardner en un artículo de Scientific American, sus reglas son las siguientes:

1. Cualquier célula viva con menos de dos vecinas vivas muere, como si la causa fuera la subpoblación.
2. Cualquier celda viva con dos o tres vecinos vivos vive en la próxima generación.
3. Cualquier célula viva con más de tres vecinos vivos muere, como por sobrepoblación.
4. Cualquier célula muerta con exactamente tres vecinos vivos se convierte en una célula viva, como por reproducción.

A pesar de su sencillez, el sistema logra una impresionante diversidad de comportamientos, oscilando entre la aparente aleatoriedad y el orden. Una de las características más evidentes del Juego de la vida es la frecuente aparición de planeadores, arreglos de celdas que esencialmente se mueven por sí mismas a través de la cuadrícula. Es posible disponer el autómata para que los planeadores interactúen para realizar cálculos, y tras mucho esfuerzo se ha demostrado que el Juego de la Vida puede emular una máquina de Turing universal. Fue visto como un tema en gran parte recreativo, y se hizo poco trabajo de seguimiento aparte de investigar las particularidades del Juego de la Vida y algunas reglas relacionadas a principios de la década de 1970.

Stephen Wolfram comenzó a trabajar de forma independiente en autómatas celulares a mediados de 1981 después de considerar cómo los patrones complejos parecían formarse en la naturaleza en violación de la Segunda Ley de la Termodinámica. Sus investigaciones fueron impulsadas inicialmente por un interés en el modelado de sistemas como las redes neuronales. Publicó su primer artículo en Reviews of Modern Physics investigando autómatas celulares elementales (Regla 30 en particular) en junio de 1983. La complejidad inesperada del comportamiento de estas reglas simples llevó a Wolfram a sospechar que la complejidad en la naturaleza puede deberse a mecanismos similares. Sin embargo, sus investigaciones lo llevaron a darse cuenta de que los autómatas celulares no eran buenos para modelar redes neuronales.Además, durante este período, Wolfram formuló los conceptos de aleatoriedad intrínseca e irreductibilidad computacional, y sugirió que la regla 110 puede ser universal, un hecho probado más tarde por el asistente de investigación de Wolfram, Matthew Cook, en la década de 1990.

Clasificación

Wolfram, en A New Kind of Science y varios artículos que datan de mediados de la década de 1980, definió cuatro clases en las que se pueden dividir los autómatas celulares y varios otros modelos computacionales simples según su comportamiento. Mientras que los estudios anteriores en autómatas celulares tendían a tratar de identificar tipos de patrones para reglas específicas, la clasificación de Wolfram fue el primer intento de clasificar las reglas mismas. En orden de complejidad las clases son:

• Clase 1: Casi todos los patrones iniciales evolucionan rápidamente hacia un estado estable y homogéneo. Cualquier aleatoriedad en el patrón inicial desaparece.
• Clase 2: Casi todos los patrones iniciales evolucionan rápidamente hacia estructuras estables u oscilantes. Parte de la aleatoriedad en el patrón inicial puede filtrarse, pero queda algo. Los cambios locales al patrón inicial tienden a permanecer locales.
• Clase 3: Casi todos los patrones iniciales evolucionan de forma pseudoaleatoria o caótica. Cualquier estructura estable que aparezca es rápidamente destruida por el ruido del entorno. Los cambios locales al patrón inicial tienden a extenderse indefinidamente.
• Clase 4: Casi todos los patrones iniciales evolucionan hacia estructuras que interactúan de formas complejas e interesantes, con la formación de estructuras locales que pueden sobrevivir durante largos períodos de tiempo. Las estructuras estables u oscilantes de clase 2 pueden ser el resultado final, pero el número de pasos necesarios para alcanzar este estado puede ser muy grande, incluso cuando el patrón inicial es relativamente simple. Los cambios locales al patrón inicial pueden extenderse indefinidamente. Wolfram ha conjeturado que muchos autómatas celulares de clase 4, si no todos, son capaces de computación universal. Esto ha sido probado para la Regla 110 y el Juego de la Vida de Conway.

Estas definiciones son de naturaleza cualitativa y hay cierto espacio para la interpretación. Según Wolfram, "... con casi cualquier esquema de clasificación general, inevitablemente hay casos que son asignados a una clase por una definición y a otra clase por otra definición. Y lo mismo ocurre con los autómatas celulares: ocasionalmente hay reglas... que muestran algunos rasgos de una clase y otros de otra". La clasificación de Wolfram se ha comparado empíricamente con un agrupamiento de las longitudes comprimidas de las salidas de los autómatas celulares.

Ha habido varios intentos de clasificar los autómatas celulares en clases formalmente rigurosas, inspirados en la clasificación de Wolfram. Por ejemplo, Culik y Yu propusieron tres clases bien definidas (y una cuarta para los autómatas que no coinciden con ninguno de estos), que a veces se denominan clases Culik-Yu; la pertenencia a estos resultó indecidible. La clase 2 de Wolfram se puede dividir en dos subgrupos de reglas estables (de punto fijo) y oscilantes (periódicas).

La idea de que hay 4 clases de sistemas dinámicos surgió originalmente del químico ganador del premio Nobel Ilya Prigogine, quien identificó estas 4 clases de sistemas termodinámicos: (1) sistemas en equilibrio termodinámico, (2) sistemas uniformes espacial/temporalmente, (3) sistemas caóticos y (4) sistemas complejos lejos del equilibrio con estructuras disipativas (ver figura 1 en el artículo de Nicolis (alumno de Prigogine)).

Reversible

Un autómata celular es reversible si, por cada configuración actual del autómata celular, existe exactamente una configuración pasada (preimagen). Si uno piensa en un autómata celular como una función que asigna configuraciones a configuraciones, la reversibilidad implica que esta función es biyectiva. Si un autómata celular es reversible, su comportamiento invertido en el tiempo también puede describirse como un autómata celular; este hecho es consecuencia del teorema de Curtis-Hedlund-Lyndon, una caracterización topológica de los autómatas celulares. Para los autómatas celulares en los que no todas las configuraciones tienen una preimagen, las configuraciones sin preimágenes se denominan patrones del Jardín del Edén.

Para autómatas celulares unidimensionales existen algoritmos conocidos para decidir si una regla es reversible o irreversible. Sin embargo, para autómatas celulares de dos o más dimensiones, la reversibilidad es indecidible; es decir, no existe ningún algoritmo que tome como entrada una regla de autómata y garantice determinar correctamente si el autómata es reversible. La demostración de Jarkko Kari está relacionada con el problema de las teselas de Wang.

Los autómatas celulares reversibles se utilizan a menudo para simular fenómenos físicos como la dinámica de gases y fluidos, ya que obedecen las leyes de la termodinámica. Dichos autómatas celulares tienen reglas especialmente construidas para ser reversibles. Dichos sistemas han sido estudiados por Tommaso Toffoli, Norman Margolus y otros. Se pueden utilizar varias técnicas para construir explícitamente autómatas celulares reversibles con inversas conocidas. Dos comunes son el autómata celular de segundo orden y el autómata celular de bloque, los cuales implican modificar la definición de un autómata celular de alguna manera. Aunque tales autómatas no satisfacen estrictamente la definición dada anteriormente, se puede demostrar que pueden ser emulados por autómatas celulares convencionales con vecindarios y números de estados suficientemente grandes. y, por lo tanto, puede considerarse un subconjunto de autómatas celulares convencionales. Por el contrario, se ha demostrado que todo autómata celular reversible puede ser emulado por un autómata celular en bloque.

Totalista

Una clase especial de autómatas celulares son los autómatas celulares totalistas. El estado de cada celda en un autómata celular totalista está representado por un número (generalmente un valor entero extraído de un conjunto finito), y el valor de una celda en el tiempo t depende solo de la suma de los valores de las celdas en su vecindad. (posiblemente incluyendo la celda misma) en el tiempo t − 1. Si el estado de la celda en el tiempo t depende tanto de su propio estado como del total de sus vecinos en el tiempo t − 1, entonces el autómata celular se llama propiamente totalista externo.El Juego de la vida de Conway es un ejemplo de un autómata celular totalista externo con valores de celda 0 y 1; Los autómatas celulares totalistas externos con la misma estructura de vecindad de Moore que Life a veces se denominan autómatas celulares similares a la vida.

Autómatas relacionados

Hay muchas generalizaciones posibles del concepto de autómata celular.

Una forma es usando algo que no sea una cuadrícula rectangular (cúbica, etc.). Por ejemplo, si un plano está en mosaico con hexágonos regulares, esos hexágonos podrían usarse como celdas. En muchos casos, los autómatas celulares resultantes son equivalentes a aquellos con cuadrículas rectangulares con vecindades y reglas especialmente diseñadas. Otra variación sería hacer que la cuadrícula sea irregular, como con los mosaicos de Penrose.

Además, las reglas pueden ser probabilísticas en lugar de deterministas. Estos autómatas celulares se denominan autómatas celulares probabilísticos. Una regla probabilística da, para cada patrón en el tiempo t, las probabilidades de que la celda central haga la transición a cada estado posible en el tiempo t + 1. A veces se usa una regla más simple; por ejemplo: "La regla es el Juego de la vida, pero en cada paso de tiempo hay una probabilidad del 0,001 % de que cada celda cambie al color opuesto".

El vecindario o las reglas pueden cambiar con el tiempo o el espacio. Por ejemplo, inicialmente el nuevo estado de una celda podría estar determinado por las celdas adyacentes horizontalmente, pero para la próxima generación se usarían las celdas verticales.

En los autómatas celulares, el nuevo estado de una célula no se ve afectado por el nuevo estado de otras células. Esto podría cambiarse para que, por ejemplo, un bloque de celdas de 2 por 2 pueda determinarse por sí mismo y las celdas adyacentes a él.

Hay autómatas continuos. Estos son como autómatas celulares totalistas, pero en lugar de que la regla y los estados sean discretos (por ejemplo, una tabla, que usa los estados {0,1,2}), se usan funciones continuas y los estados se vuelven continuos (generalmente valores en [0,1 ]). El estado de una ubicación es un número finito de números reales. Ciertos autómatas celulares pueden producir difusión en patrones líquidos de esta manera.

Los autómatas espaciales continuos tienen un continuo de ubicaciones. El estado de una ubicación es un número finito de números reales. El tiempo también es continuo y el estado evoluciona de acuerdo con ecuaciones diferenciales. Un ejemplo importante son las texturas de reacción-difusión, ecuaciones diferenciales propuestas por Alan Turing para explicar cómo las reacciones químicas podrían crear las rayas en las cebras y las manchas en los leopardos. Cuando estos son aproximados por autómatas celulares, a menudo producen patrones similares. MacLennan [1] considera los autómatas espaciales continuos como un modelo de computación.

Hay ejemplos conocidos de autómatas espaciales continuos, que exhiben fenómenos de propagación análogos a los planeadores en el Juego de la Vida.

Los autómatas de reescritura de gráficos son extensiones de los autómatas celulares basados ​​en sistemas de reescritura de gráficos.

Autómatas celulares elementales

El autómata celular no trivial más simple sería unidimensional, con dos estados posibles por celda, y los vecinos de una celda definidos como las celdas adyacentes a ambos lados. Una celda y sus dos vecinos forman un vecindario de 3 celdas, por lo que hay 2 = 8 patrones posibles para un vecindario. Una regla consiste en decidir, para cada patrón, si la celda será un 1 o un 0 en la próxima generación. Entonces hay 2 = 256 reglas posibles.

Estos 256 autómatas celulares generalmente se denominan por su código Wolfram, una convención de nomenclatura estándar inventada por Wolfram que le da a cada regla un número del 0 al 255. Varios artículos han analizado y comparado estos 256 autómatas celulares. Los autómatas celulares de regla 30 y regla 110 son particularmente interesantes. Las siguientes imágenes muestran el historial de cada una cuando la configuración inicial consta de un 1 (en la parte superior de cada imagen) rodeado de 0. Cada fila de píxeles representa una generación en la historia del autómata, siendo t = 0 la fila superior. Cada píxel es de color blanco para 0 y negro para 1.

Regla 30 autómata celular

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

La regla 30 exhibe un comportamiento de clase 3, lo que significa que incluso los patrones de entrada simples como el que se muestra conducen a historias caóticas y aparentemente aleatorias.

Regla 110 autómata celular

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

La Regla 110, como el Juego de la Vida, exhibe lo que Wolfram llama comportamiento de clase 4, que no es completamente aleatorio ni completamente repetitivo. Las estructuras localizadas aparecen e interactúan de varias maneras que parecen complicadas. En el curso del desarrollo de Un nuevo tipo de ciencia, como asistente de investigación de Wolfram en 1994, Matthew Cook demostró que algunas de estas estructuras eran lo suficientemente ricas como para sustentar la universalidad. Este resultado es interesante porque la regla 110 es un sistema unidimensional extremadamente simple y difícil de diseñar para realizar un comportamiento específico. Este resultado, por lo tanto, proporciona un apoyo significativo a la opinión de Wolfram de que los sistemas de clase 4 tienen una probabilidad inherente de ser universales. Cook presentó su prueba en una conferencia del Instituto Santa Fe sobre autómatas celulares en 1998, pero Wolfram bloqueó la prueba para que no se incluyera en las actas de la conferencia, ya que Wolfram no quería que la prueba se anunciara antes de la publicación de A New Kind of Science. En 2004, la prueba de Cook finalmente se publicó en la revista Complex Systems de Wolfram.(Vol. 15, No. 1), más de diez años después de que a Cook se le ocurriera. La regla 110 ha sido la base de algunas de las máquinas de Turing universales más pequeñas.

Espacio de reglas

Una regla de autómata celular elemental se especifica mediante 8 bits, y se puede considerar que todas las reglas de autómatas celulares elementales se asientan en los vértices del hipercubo de unidades de 8 dimensiones. Este hipercubo unitario es el espacio de reglas del autómata celular. Para los autómatas celulares del vecino más cercano, una regla se especifica mediante 2 = 32 bits, y el espacio de reglas del autómata celular es un hipercubo de unidades de 32 dimensiones. La distancia entre dos reglas se puede definir por el número de pasos necesarios para moverse desde un vértice, que representa la primera regla, y otro vértice, que representa otra regla, a lo largo del borde del hipercubo. Esta distancia de regla a regla también se llama distancia de Hamming.

El espacio de reglas de autómatas celulares nos permite preguntarnos si las reglas con un comportamiento dinámico similar son "cercanas" entre sí. Dibujar gráficamente un hipercubo de alta dimensión en el plano bidimensional sigue siendo una tarea difícil, y un localizador tosco de una regla en el hipercubo es el número de bit-1 en la cadena de 8 bits para reglas elementales (o cadena de 32 bits para reglas elementales). las reglas del vecino más próximo). Dibujar las reglas en diferentes clases de Wolfram en estas porciones del espacio de reglas muestra que las reglas de clase 1 tienden a tener un número más bajo de bits 1, por lo tanto, se ubican en una región del espacio, mientras que las reglas de clase 3 tienden a tener una proporción más alta (50 %) de bit-1s.

Para un espacio de reglas de autómatas celulares más grande, se muestra que las reglas de clase 4 se ubican entre las reglas de clase 1 y clase 3. Esta observación es la base de la frase borde del caos y recuerda la transición de fase en la termodinámica.

Aplicaciones

Biología

Varios procesos biológicos ocurren, o pueden ser simulados, por autómatas celulares.

Algunos ejemplos de fenómenos biológicos modelados por autómatas celulares con un espacio de estado simple son:

• Los patrones de algunas conchas marinas, como las de los géneros Conus y Cymbiola, son generados por autómatas celulares naturales. Las células de pigmento residen en una banda estrecha a lo largo del borde de la concha. Cada célula segrega pigmentos de acuerdo con la actividad activadora e inhibidora de sus células pigmentarias vecinas, obedeciendo a una versión natural de una regla matemática. La banda de células deja el patrón de color en el caparazón a medida que crece lentamente. Por ejemplo, la especie extendida Conus textile tiene un patrón que se asemeja al autómata celular de la regla 30 de Wolfram.
• Las plantas regulan su ingesta y pérdida de gases a través de un mecanismo de autómata celular. Cada estoma de la hoja actúa como una célula.
• Los patrones de ondas en movimiento en la piel de los cefalópodos se pueden simular con un autómata celular bidimensional de dos estados, cada estado corresponde a un cromatóforo expandido o retraído.
• Se han inventado autómatas de umbral para simular neuronas y se pueden simular comportamientos complejos como el reconocimiento y el aprendizaje.
• Los fibroblastos tienen similitudes con los autómatas celulares, ya que cada fibroblasto solo interactúa con sus vecinos.

Además, los fenómenos biológicos que requieren un modelado explícito de las velocidades de los agentes (por ejemplo, aquellos involucrados en la migración celular colectiva) pueden ser modelados por autómatas celulares con un espacio de estado y reglas más complejos, como los autómatas celulares de gas de red biológica. Estos incluyen fenómenos de gran importancia médica, tales como:

• Caracterización de diferentes modos de invasión metastásica.
• El papel de la heterogeneidad en el desarrollo de carcinomas agresivos.
• Cambio fenotípico durante la proliferación tumoral.

Química

La reacción de Belousov-Zhabotinsky es un oscilador químico espacio-temporal que se puede simular mediante un autómata celular. En la década de 1950, AM Zhabotinsky (ampliando el trabajo de BP Belousov) descubrió que cuando una capa delgada y homogénea de una mezcla de ácido malónico, bromato acidificado y una sal cérica se mezclaban y dejaban intactas, fascinantes patrones geométricos como círculos concéntricos y las espirales se propagan a través del medio. En la sección "Recreaciones informáticas" del número de agosto de 1988 de Scientific American, AK Dewdney habló sobre un autómata celular desarrollado por Martin Gerhardt y Heike Schuster de la Universidad de Bielefeld (Alemania). Este autómata produce patrones de onda que se asemejan a los de la reacción de Belousov-Zhabotinsky.

Física

Los autómatas celulares probabilísticos se utilizan en física estadística y de materia condensada para estudiar fenómenos como la dinámica de fluidos y las transiciones de fase. El modelo de Ising es un ejemplo prototípico, en el que cada celda puede estar en cualquiera de dos estados llamados "arriba" y "abajo", haciendo una representación idealizada de un imán. Al ajustar los parámetros del modelo, se puede variar la proporción de celdas que se encuentran en el mismo estado, de manera que ayuden a explicar cómo los ferroimanes se desmagnetizan cuando se calientan. Además, los resultados del estudio de la transición de fase de desmagnetización se pueden transferir a otras transiciones de fase, como la evaporación de un líquido a gas; esta conveniente aplicabilidad cruzada se conoce como universalidad.La transición de fase en el modelo bidimensional de Ising y otros sistemas en su clase de universalidad ha sido de particular interés, ya que requiere una teoría de campos conformes para comprenderla en profundidad. Otros autómatas celulares que han tenido importancia en la física incluyen los autómatas de gas reticular, que simulan flujos de fluidos.

Informática, codificación y comunicación.

Los procesadores de autómatas celulares son implementaciones físicas de los conceptos de CA, que pueden procesar información computacionalmente. Los elementos de procesamiento están dispuestos en una cuadrícula regular de celdas idénticas. La cuadrícula suele ser un mosaico cuadrado, o teselado, de dos o tres dimensiones; otras teselaciones son posibles, pero aún no se utilizan. Los estados de las celdas están determinados únicamente por las interacciones con las celdas vecinas adyacentes. No existe ningún medio para comunicarse directamente con las células más lejanas.Una de tales configuraciones de matrices de procesadores de autómatas celulares es la matriz sistólica. La interacción celular puede ser a través de carga eléctrica, magnetismo, vibración (fonones a escalas cuánticas) o cualquier otro medio físicamente útil. Esto se puede hacer de varias maneras para que no se necesiten cables entre los elementos. Esto es muy diferente a los procesadores que se usan en la mayoría de las computadoras hoy en día (diseños de von Neumann) que se dividen en secciones con elementos que pueden comunicarse con elementos distantes a través de cables.

La regla 30 se sugirió originalmente como un posible cifrado de bloque para su uso en criptografía. Se pueden utilizar autómatas celulares bidimensionales para construir un generador de números pseudoaleatorios.

Se han propuesto autómatas celulares para la criptografía de clave pública. La función unidireccional es la evolución de una CA finita cuya inversa se cree que es difícil de encontrar. Dada la regla, cualquiera puede calcular fácilmente los estados futuros, pero parece ser muy difícil calcular los estados anteriores. Los autómatas celulares también se han aplicado para diseñar códigos de corrección de errores.

Otros problemas que se pueden resolver con autómatas celulares incluyen:

• Problema de sincronización del pelotón de fusilamiento
• Problema de la mayoría

Música y arte generativo

Los autómatas celulares se han utilizado en música generativa y composición de música evolutiva y generación de terreno de procedimiento en videojuegos.

Reglas específicas

Los tipos específicos de autómatas celulares incluyen:

• el cerebro de brian
• Autómata celular de Codd
• CoDi
• hormiga de langton
• Bucles de Langton
• Autómatas celulares Nobili
• regla 90
• Regla 184
• Autómata celular de Von Neumann
• Mundo de alambre
• El juego de la vida de Conway