Hispanopedia Wiki
Articulo de referencia

Autómata celular

El Glider Gun de Gosper crea " planeadores " en el autómata celular Juego de la vida de Conway [ 1 ] Un autómata celular (pl. autómatas celulares , abreviatura CA ) es un modelo...

Hispanopedia WikiContenido en espanolLectura gratuita

El Glider Gun de Gosper crea " planeadores " en el autómata celular Juego de la vida de Conway [ 1 ]

Un autómata celular (pl. autómatas celulares , abreviatura CA ) 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 teselación , estructuras homogéneas , estructuras celulares , estructuras de teselación y arreglos iterativos . [ 2 ] Los autómatas celulares han encontrado aplicación en diversas áreas, incluyendo la física , la biología teórica y el modelado de microestructuras .

Un autómata celular consiste en una cuadrícula regular de celdas , cada una en uno de un número finito de estados , como encendido y apagado (a diferencia de una red de mapas acoplados ). La cuadrícula puede tener cualquier número finito de dimensiones. Para cada celda, se define un conjunto de celdas llamado su vecindario en relación con la celda especificada. Se selecciona un estado inicial (tiempo t  =  0) asignando un estado a cada celda. Se crea una nueva generación (avanzando t en 1), de acuerdo con alguna regla fija (generalmente, una función matemática) [ 3 ] 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 vecindario. Típicamente, 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 cuadrícula simultáneamente, [ 4 ] aunque se conocen excepciones, como el autómata celular estocástico y el autómata celular asíncrono .

El concepto fue concebido originalmente en la década de 1940 por Stanislaw Ulam y John von Neumann, quienes eran compañeros en el Laboratorio Nacional de Los Alamos . Si bien fue estudiado por algunos durante las décadas de 1950 y 1960, no fue hasta la década de 1970, con el Juego de la Vida de Conway , un autómata celular bidimensional, que el interés en el tema se extendió más allá del ámbito académico. En la década de 1980, Stephen Wolfram se dedicó al 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-completa .

Las clasificaciones principales de autómatas celulares, según Wolfram, se numeran 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 mayormente estables u oscilantes, autómatas en los que los patrones evolucionan de manera aparentemente caótica, y autómatas en los que los patrones se vuelven extremadamente complejos y pueden durar mucho tiempo, con estructuras locales estables. Se cree que esta última clase es computacionalmente universal , o capaz de simular una máquina de Turing . Tipos especiales de autómatas celulares son los reversibles , donde una sola configuración conduce directamente a la siguiente, y los totalísticos , en los que el valor futuro de las células individuales solo depende del valor total de un grupo de células vecinas. Los autómatas celulares pueden simular una variedad de sistemas del mundo real, incluidos los biológicos y químicos.

Descripción general

Las celdas rojas representan el vecindario de Moore para la celda azul.
Las celdas rojas constituyen el vecindario de von Neumann de la celda azul. El "vecindario cruzado" de rango 2 también incluye las celdas rosas.

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 celdas. Cada cuadrado se llama "celda" y cada celda tiene dos estados posibles: negro o blanco. El vecindario de una celda son las celdas cercanas, generalmente adyacentes. Los dos tipos más comunes de vecindarios son el vecindario de von Neumann y el vecindario de Moore . [ 5 ] El primero, que recibe su nombre del teórico fundador del autómata celular, consta de las cuatro celdas adyacentes ortogonalmente . [ 5 ] El segundo incluye el vecindario de von Neumann, así como las cuatro celdas adyacentes diagonalmente. [ 5 ] Para una celda de este tipo y su vecindario de Moore, hay 512 (= 2 9 ) patrones posibles. Para cada uno de los 512 patrones posibles, la tabla de reglas indicaría si la celda central será negra o blanca en el siguiente intervalo de tiempo. El Juego de la Vida de Conway es una versión popular de este modelo. Otro tipo de vecindario común es el vecindario de von Neumann extendido , que incluye las dos celdas más cercanas en cada dirección ortogonal, para un total de ocho. [ 5 ] La ecuación general para el número total de autómatas posibles es k k s , 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) utilizadas para determinar el siguiente estado de la celda. [ 6 ] Por lo tanto, en el sistema bidimensional con un vecindario de Moore, el número total de autómatas posibles sería 2 2 9 , o1,34 × 10 154 .

Generalmente se asume que cada célula del universo comienza en el mismo estado, excepto un número finito de células en otros estados; la asignación de valores de estado se denomina configuración . [ 7 ] De forma más general, a veces se asume que el universo comienza cubierto por un patrón periódico, y que solo un número finito de células viola dicho patrón. Esta última suposición es común en los autómatas celulares unidimensionales.

Una forma toroidal (el toroide )

Los autómatas celulares suelen simularse en una cuadrícula finita en lugar de una infinita. En dos dimensiones, el universo sería un rectángulo en vez de un plano infinito. El problema evidente de las cuadrículas finitas radica en cómo gestionar las celdas de los bordes. Su gestión afectará a los valores de todas las celdas de la cuadrícula. Un método posible consiste en permitir que los valores de dichas celdas permanezcan constantes. Otro método consiste en definir vecindarios diferentes para estas celdas. Se podría decir que tienen menos vecinos, pero entonces también habría que definir nuevas reglas para las celdas situadas en los bordes. Estas celdas suelen tratarse con condiciones de contorno periódicas, lo que da lugar a una disposición toroidal : cuando una celda sale por la parte superior, otra entra en la posición correspondiente en la parte inferior, y cuando una sale por la izquierda, otra entra por la derecha. (Esto simula esencialmente un teselado periódico infinito, y en el campo de las ecuaciones diferenciales parciales a veces se hace referencia a condiciones de contorno periódicas ). Esto se puede visualizar como unir los bordes izquierdo y derecho del rectángulo para formar un tubo, y luego unir los bordes superior e inferior del tubo para formar un toroide (forma de rosquilla). Los universos de otras dimensiones se manejan de manera similar. Esto resuelve problemas de contorno con vecindarios, 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, el vecindario de una celda x i t es { x i −1 t −1 , x i t −1 , x i +1 t −1 }, donde t es el paso de tiempo (vertical) e i es el índice (horizontal) en una generación.

Historia

Stanisław Ulam , mientras trabajaba en el Laboratorio Nacional de Los Alamos en la década de 1940, estudió el crecimiento de cristales, utilizando una red reticular simple como modelo. [ 8 ] Al mismo tiempo, John von Neumann —colega de Ulam en Los Alamos— trabajaba en el problema de los sistemas autorreplicantes . [ 9 ] El diseño inicial de Von Neumann se basaba en la noción de un robot construyendo otro robot. Este diseño se conoce como el modelo cinemático. [ 10 ] [ 11 ] A medida que desarrollaba este diseño, von Neumann se dio cuenta de la gran dificultad de construir un robot autorreplicante y del gran costo de proporcionarle 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. [ 9 ] Ulam fue quien sugirió utilizar un sistema discreto para crear un modelo reduccionista de autorreplicación. [ 12 ] [ 13 ] Nils Aall Barricelli realizó muchas de las primeras exploraciones de estos modelos de vida artificial .

John von Neumann , placa de identificación de Los Álamos

Ulam y von Neumann crearon un método para calcular el movimiento de líquidos a finales de la década de 1950. El concepto fundamental del método consistía en considerar un líquido como un grupo de unidades discretas y calcular el movimiento de cada una basándose en el comportamiento de sus vecinas. [ 14 ] Así nació el primer sistema de autómatas celulares. Al igual que la red reticular de Ulam, los autómatas celulares de von Neumann son bidimensionales, con su autorreplicador implementado algorítmicamente. El resultado fue un copiador y constructor universal que operaba dentro de un autómata celular con un vecindario pequeño (solo las celdas que se tocan son vecinas; para los autómatas celulares de von Neumann, solo las celdas ortogonales ), y con 29 estados por celda. [ 15 ] Von Neumann proporcionó una prueba de existencia de que un patrón particular haría copias infinitas de sí mismo dentro del universo celular dado, diseñando una configuración de 200 000 celdas que podía hacerlo. [ 15 ] Este diseño se conoce como el modelo de teselación y se denomina constructor universal de von Neumann . [ 16 ]

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. [ 17 ] Su motivación específica fue la descripción matemática de la conducción de impulsos en 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. [ 17 ] [ 18 ] Un verdadero modelo de autómata celular de medios excitables fue desarrollado y estudiado por JM Greenberg y SP Hastings en 1978; véase 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. [ 19 ]

En la década de 1960, los autómatas celulares se estudiaron como un tipo particular de sistema dinámico y se estableció por primera vez la conexión con el campo matemático de la dinámica simbólica . En 1969, Gustav A. Hedlund recopiló muchos resultados siguiendo este punto de vista [ 20 ] en lo que todavía se considera un artículo fundamental 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 los 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 , en el que proponía 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 denominado física digital . [ 21 ]

También en 1969, el científico informático Alvy Ray Smith completó una disertación doctoral en Stanford sobre la Teoría de Autómatas Celulares, el primer tratamiento matemático de los CA como una clase general de computadoras. Muchos artículos surgieron de esta disertación: mostró la equivalencia de vecindarios de varias formas, cómo reducir un vecindario de Moore a un vecindario de von Neumann o cómo reducir cualquier vecindario a un vecindario de von Neumann. [ 22 ] Probó que los CA bidimensionales son universales en computación, introdujo los CA unidimensionales y mostró que también son universales en computación, incluso con vecindarios simples. [ 23 ] Mostró cómo subsumir la prueba compleja de von Neumann de universalidad de construcción (y por lo tanto máquinas autorreproductoras) en una consecuencia de la universalidad de computación en un CA unidimensional. [ 24 ] Concebido como la introducción a la edición alemana del libro de von Neumann sobre CA, escribió un estudio del campo con docenas de referencias a artículos de muchos autores en muchos países a lo largo de una década de trabajo, a menudo pasados ​​por alto por los investigadores modernos de CA. [ 25 ]

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

  1. Cualquier célula viva con menos de dos vecinas vivas muere, como si fuera a causa de la baja población celular.
  2. Cualquier célula activa con dos o tres células vecinas activas perdura hasta la siguiente generación.
  3. Cualquier célula viva con más de tres vecinas vivas muere, como si se tratara de una sobrepoblación.
  4. Cualquier célula muerta que tenga exactamente tres células vivas vecinas se convierte en una célula viva, como si se reprodujera.

A pesar de su simplicidad, el sistema logra una impresionante diversidad de comportamiento, fluctuando entre aparente aleatoriedad y orden. Una de las características más evidentes del Juego de la Vida es la frecuente aparición de deslizadores , conjuntos de celdas que esencialmente se mueven por sí mismas a través de la cuadrícula. Es posible organizar el autómata de manera que los deslizadores interactúen para realizar cálculos, y después de mucho esfuerzo se ha demostrado que el Juego de la Vida puede emular una máquina de Turing universal . [ 27 ] Se consideró un tema principalmente recreativo, y se realizó poco trabajo de seguimiento más allá de investigar las particularidades del Juego de la Vida y algunas reglas relacionadas a principios de la década de 1970. [ 28 ]

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 . [ 29 ] Sus investigaciones fueron impulsadas inicialmente por el deseo de modelar sistemas como las redes neuronales que se encuentran en los cerebros. [ 29 ] Publicó su primer artículo en Reviews of Modern Physics investigando autómatas celulares elementales ( Regla 30 en particular) en junio de 1983. [ 2 ] [ 29 ] La inesperada complejidad del comportamiento de estas reglas simples llevó a Wolfram a sospechar que la complejidad en la naturaleza puede deberse a mecanismos similares. [ 29 ] Sin embargo, sus investigaciones lo llevaron a darse cuenta de que los autómatas celulares eran deficientes para modelar redes neuronales. [ 29 ] Además, durante este período Wolfram formuló los conceptos de aleatoriedad intrínseca e irreductibilidad computacional , [ 30 ] y sugirió que la Regla 110 podría ser universal , un hecho que posteriormente demostró el asistente de investigación de Wolfram, Matthew Cook, en la década de 1990. [ 31 ]

Clasificación

Wolfram, en su obra *A New Kind of Science* y en varios artículos publicados a mediados de la década de 1980, definió cuatro clases en las que se pueden dividir los autómatas celulares y otros modelos computacionales sencillos según su comportamiento. Si bien los estudios previos sobre autómatas celulares tendían a intentar identificar tipos de patrones para reglas específicas, la clasificación de Wolfram fue el primer intento de clasificar las reglas en sí 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. [ 32 ]
  • Clase 2: Casi todos los patrones iniciales evolucionan rápidamente hacia estructuras estables u oscilantes. Parte de la aleatoriedad del patrón inicial puede filtrarse, pero otra parte permanece. Los cambios locales en el patrón inicial tienden a permanecer locales. [ 32 ]
  • Clase 3: Casi todos los patrones iniciales evolucionan de manera pseudoaleatoria o caótica. Cualquier estructura estable que aparezca es rápidamente destruida por el ruido circundante. Los cambios locales en el patrón inicial tienden a propagarse indefinidamente. [ 32 ]
  • Clase 4: Casi todos los patrones iniciales evolucionan hacia estructuras que interactúan de maneras complejas e interesantes, con la formación de estructuras locales que pueden sobrevivir durante largos períodos de tiempo. [ 33 ] Las estructuras estables u oscilantes de tipo 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 propagarse indefinidamente. Wolfram ha conjeturado que muchos autómatas celulares de clase 4, si no todos, son capaces de computación universal . Esto se ha demostrado para la Regla 110 y el Juego de la Vida de Conway.

Estas definiciones son de naturaleza cualitativa y admiten cierta interpretación. Según Wolfram, «…con casi cualquier esquema de clasificación general, inevitablemente hay casos que se asignan a una clase según una definición y a otra clase según otra definición. Y lo mismo ocurre con los autómatas celulares: ocasionalmente hay reglas… que muestran algunas características de una clase y algunas de otra». [ 34 ]

Se han realizado varios intentos de clasificar los autómatas celulares en clases formalmente rigurosas, inspiradas 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 se ajustan a ninguna de ellas), que a veces se denominan clases de Culik-Yu; la pertenencia a estas resultó indecidible . [ 35 ] [ 36 ] [ 37 ] La clase 2 de Wolfram se puede dividir en dos subgrupos de reglas estables (de punto fijo) y oscilantes (periódicas). [ 38 ]

La idea de que existen 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 espacial y temporalmente uniformes, (3) sistemas caóticos y (4) sistemas complejos lejos del equilibrio con estructuras disipativas (véase la figura 1 en el artículo de 1974 de Nicolis, estudiante de Prigogine). [ 39 ]

Reversible

Un autómata celular es reversible si, para cada configuración actual del autómata celular, existe exactamente una configuración pasada ( preimagen ). [ 40 ] Si se piensa en un autómata celular como una función que mapea configuraciones a configuraciones, la reversibilidad implica que esta función es biyectiva . [ 40 ] 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. [ 41 ] [ 42 ] 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 . [ 43 ]

Para autómatas celulares unidimensionales, existen algoritmos conocidos para decidir si una regla es reversible o irreversible. [ 44 ] [ 45 ] Sin embargo, para autómatas celulares de dos o más dimensiones, la reversibilidad es indecidible ; es decir, no existe un 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 teselado de Wang tiles . [ 46 ] Cuando un autómata 2D no es reversible, a menudo la demostración puede ser trivial, ya que los patrones distintos que se mapean al mismo estado pueden ser bastante comunes.

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 poseen reglas especialmente diseñadas para ser reversibles. Estos 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 inversos conocidos. Dos de las más comunes son el autómata celular de segundo orden y el autómata celular de bloques , ambos implican modificar la definición de un autómata celular de alguna manera. Si bien estos autómatas no satisfacen estrictamente la definición anterior, se puede demostrar que pueden ser emulados por autómatas celulares convencionales con vecindarios y número de estados suficientemente grandes, y por lo tanto pueden considerarse un subconjunto de los autómatas celulares convencionales. A la inversa, se ha demostrado que todo autómata celular reversible puede ser emulado por un autómata celular de bloques. [ 47 ] [ 48 ]

Totalitario

Una clase especial de autómatas celulares son los autómatas celulares totalísticos . El estado de cada celda en un autómata celular totalístico se representa mediante un número (generalmente un valor entero extraído de un conjunto finito), y el valor de una celda en el instante t depende únicamente de la suma de los valores de las celdas en su vecindario (posiblemente incluyendo la propia celda) en el instante t − 1. [ 49 ] [ 50 ]   

Si el estado de la celda en el instante t depende tanto de su propio estado como del total de sus vecinas en el instante t − 1, entonces el autómata celular se denomina propiamente totalista externo . [ 50 ] El Juego de la Vida de Conway es totalista externo (pero no totalista), con valores de celda 0 y 1. Los autómatas celulares totalistas externos con la misma estructura de vecindad de Moore que el Juego de la Vida a veces se denominan autómatas celulares similares a la vida . [ 51 ] [ 52 ]   

En términos más generales, un conjunto de reglas isotrópicas es aquel que no es necesariamente totalitario externo, pero que aún posee todas las simetrías de reflexión. En el caso de un autómata celular en una cuadrícula cuadrada, el grupo de simetrías es D8 .

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

Un autómata celular basado en celdas hexagonales en lugar de cuadradas (regla 34/2).

Una forma es utilizando una cuadrícula distinta a la rectangular (cúbica, etc. ). Por ejemplo, si un plano se cubre con hexágonos regulares , estos podrían usarse como celdas. En muchos casos, los autómatas celulares resultantes son equivalentes a los que utilizan cuadrículas rectangulares con vecindades y reglas especialmente diseñadas. Otra variante sería hacer que la cuadrícula misma sea irregular, como con las teselas de Penrose . [ 53 ]

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 proporciona, para cada patrón en el instante t , las probabilidades de que la célula central transite a cada estado posible en el instante t  +  1. A veces se utiliza una regla más simple; por ejemplo: «La regla es el Juego de la Vida, pero en cada paso de tiempo existe una probabilidad del 0,001 % de que cada célula transite al color opuesto».

El vecindario o las reglas podrían 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 siguiente 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 las demás. Esto podría modificarse para que, por ejemplo, un bloque de células de 2x2 pueda determinarse a partir de sí mismo y de las células adyacentes.

Existen autómatas continuos . Estos son similares a los autómatas celulares totalitarios, pero en lugar de que la regla y los estados sean discretos ( por ejemplo , una tabla con estados {0,1,2}), se utilizan 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 generar patrones de difusión en líquidos de esta manera.

Los autómatas espaciales continuos poseen 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 según 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 de las cebras y las manchas de los leopardos. [ 54 ] Cuando estas se aproximan mediante autómatas celulares, a menudo producen patrones similares. MacLennanConsidera los autómatas espaciales continuos como un modelo de computación.

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

Los autómatas de reescritura de grafos son extensiones de los autómatas celulares basados ​​en sistemas de reescritura de grafos . [ 56 ]

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 se definen como las celdas adyacentes a cada lado de ella. 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 siguiente generación. Hay entonces 2⁸ =  256  reglas posibles. [ 6 ]

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

Estos 256 autómatas celulares se conocen generalmente por su código Wolfram , una convención de nomenclatura estándar inventada por Wolfram que asigna a cada regla un número del 0 al 255. Diversos estudios han analizado y comparado los distintos casos entre los 256 autómatas celulares (muchos son trivialmente isomorfos). Los autómatas celulares de las reglas 30 , 90 , 110 y 184 son particularmente interesantes. Las imágenes a continuación muestran el historial de las reglas 30 y 110 cuando la configuración inicial consiste en un 1 (en la parte superior de cada imagen) rodeado de 0. Cada fila de píxeles representa una generación en el historial del autómata, siendo t = 0 la fila superior. Cada píxel está coloreado de blanco para 0 y de negro para  1.

Regla 30

La regla 30 muestra un comportamiento de clase 3 , lo que significa que incluso patrones de entrada simples como el que se muestra conducen a historiales caóticos y aparentemente aleatorios.

256 iteraciones de la Regla 110

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 aleatorio ni completamente repetitivo. Aparecen estructuras localizadas que interactúan de diversas maneras aparentemente complejas. Durante el desarrollo de *A New Kind of Science* , Matthew Cook, asistente de investigación de Wolfram en 1994, 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 que realice un comportamiento específico. Por lo tanto, este resultado proporciona un apoyo significativo a la visión de Wolfram de que los sistemas de clase 4 tienen una probabilidad inherente de ser universales. Cook presentó su demostración en una conferencia del Instituto Santa Fe sobre Autómatas Celulares en 1998, pero Wolfram impidió que la demostración se incluyera en las actas de la conferencia, ya que no quería que se anunciara antes de la publicación de * A New Kind of Science* . [ 57 ] En 2004, la demostración 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 Cook la formulara. La regla 110 ha sido la base de algunas de las máquinas de Turing universales más pequeñas. [ 58 ]

Espacio de reglas

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

El espacio de reglas de los autómatas celulares nos permite plantearnos si las reglas con un comportamiento dinámico similar están "cerca" entre sí. Dibujar gráficamente un hipercubo de alta dimensión en un plano bidimensional sigue siendo una tarea difícil, y un localizador rudimentario de una regla en el hipercubo es el número de bits 1 en la cadena de 8 bits para las reglas elementales (o la cadena de 32 bits para las reglas del vecino más próximo). Al dibujar las reglas en diferentes clases de Wolfram en estas secciones del espacio de reglas, se observa que las reglas de clase 1 tienden a tener un menor número de bits 1, ubicándose así en una región del espacio, mientras que las reglas de clase 3 tienden a tener una mayor proporción (50%) de bits 1. [ 38 ]

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

Aplicaciones

Biología

El tejido Conus exhibe un patrón de autómata celular en su capa exterior. [ 60 ]

Se pueden simular varios procesos o fenómenos biológicos utilizando autómatas celulares, que se consideran un tipo específico de modelo basado en agentes en tales contextos de aplicación. [ 61 ] [ 62 ] En estas simulaciones biológicas, es común que las células del autómata celular se identifiquen con células biológicas. [ 63 ]

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

  • Los patrones de algunas conchas marinas , como las de los géneros Conus y Cymbiola , se generan mediante autómatas celulares naturales. Las células pigmentarias se encuentran en una banda estrecha a lo largo del borde de la concha. Cada célula secreta pigmentos según la actividad activadora e inhibidora de sus células pigmentarias vecinas, siguiendo una versión natural de una regla matemática. [ 60 ] La banda celular deja el patrón de color en la concha a medida que crece lentamente. Por ejemplo, la especie Conus textile, de amplia distribución , presenta un patrón similar al autómata celular de la regla 30 de Wolfram . [ 60 ]
  • Las plantas regulan la absorción y la pérdida de gases mediante un mecanismo de autómata celular. Cada estoma de la hoja actúa como una célula. [ 64 ]
  • Los patrones de ondas en movimiento sobre la piel de los cefalópodos pueden simularse con un autómata celular bidimensional de dos estados, donde cada estado corresponde a un cromatóforo expandido o retraído . [ 65 ]
  • Se han inventado autómatas de umbral para simular neuronas , y se pueden simular comportamientos complejos como el reconocimiento y el aprendizaje. [ 66 ]
  • Los fibroblastos presentan similitudes con los autómatas celulares, ya que cada fibroblasto solo interactúa con sus vecinos. [ 67 ]

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

Química

La reacción de Belousov-Zhabotinsky es un oscilador químico espacio-temporal que puede simularse mediante un autómata celular. En la década de 1950, A. M. Zhabotinsky (ampliando el trabajo de B. P. Belousov ) descubrió que al mezclar una capa delgada y homogénea de ácido malónico , bromato acidificado y una sal cíclica, y dejarla reposar, se propagaban fascinantes patrones geométricos, como círculos concéntricos y espirales, a través del medio. En la sección "Recreaciones por computadora" del número de agosto de 1988 de Scientific American , [ 71 ] A. K. Dewdney analizó un autómata celular [ 72 ] desarrollado por Martin Gerhardt y Heike Schuster de la Universidad de Bielefeld (Alemania). Este autómata produce patrones de ondas que se asemejan a los de la reacción de Belousov-Zhabotinsky. Combinando la unión a una sola partícula del agregado en crecimiento, siguiendo el modelo seminal de Witten y Sander [ 73 ] para simular el crecimiento limitado por difusión con la unión a posiciones de inflexión como ya propusieron Kossel y Stranski en la década de 1920, véase [ 74 ] para la versión limitada por la cinética de la unión, Goranova et al. [ 75 ] propusieron un modelo para la codeposición electroquímica de dos cationes metálicos.

Física

Visualización de un autómata de gas reticular. Los tonos de gris de los píxeles individuales son proporcionales a la densidad de partículas de gas (entre 0 y 4) en cada píxel. El gas está rodeado por una capa de celdas negras que actúan como reflectores para crear un espacio cerrado.

Los autómatas celulares probabilísticos se utilizan en la física estadística y de la 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 uno de dos estados llamados "arriba" y "abajo", lo que constituye una representación idealizada de un imán . Ajustando los parámetros del modelo, se puede variar la proporción de celdas que se encuentran en el mismo estado, lo que ayuda a explicar cómo los ferromagnetos se desmagnetizan al calentarse. 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 en un gas; esta conveniente aplicabilidad cruzada se conoce como universalidad . [ 76 ] [ 77 ] La transición de fase en el modelo de Ising bidimensional y otros sistemas de su clase de universalidad ha sido de particular interés, ya que requiere la teoría de campos conformes para su comprensión profunda. [ 78 ]

Otros autómatas celulares que han sido significativos en física incluyen los autómatas de gas reticular , que simulan flujos de fluidos. En una serie de trabajos [ 79 ] [ 80 ] [ 81 ] [ 82 ] se propuso el llamado Autómata Celular Vicinal (vicCA) y se desarrolló aún más para modelar el crecimiento y la sublimación posiblemente inestables de superficies de cristales vicinales en 1+1D. Además de que los eventos de unión/desprendimiento están codificados en las reglas del CA, los adátomos sobre el vicinal forman una capa delgada, y su movimiento térmico se modela mediante un módulo de Monte Carlo. [ 79 ] [ 81 ] Un paso decisivo más allá fue la transición del modelo a 2+1D, [ 83 ] donde se obtuvieron varias estructuras diferentes, a las que los autores se refirieron como "criaturas vecinales": grupos de escalones, meandros de escalones, nanopilares, nanocables, etc. [ 83 ] El modelo vicCA fue ampliamente utilizado por Alexey Redkov [ 84 ] para desarrollar un algoritmo de aprendizaje automático sobre él, acelerando significativamente los cálculos en un factor de 10 5 al tiempo que permitía la clasificación sistemática de los fenómenos observados.

Informática, programación y comunicación

Los procesadores de autómatas celulares son implementaciones físicas de conceptos de autómatas celulares, capaces de procesar información computacionalmente. Los elementos de procesamiento se organizan en una cuadrícula regular de celdas idénticas. La cuadrícula suele ser un mosaico cuadrado, o teselación , de dos o tres dimensiones; existen otros mosaicos posibles, pero aún no se utilizan. Los estados de las celdas se determinan únicamente por las interacciones con las celdas vecinas adyacentes. No existe ningún medio para comunicarse directamente con las celdas más distantes. [ 85 ] Una de estas configuraciones de matriz de procesadores de autómatas celulares es la matriz sistólica . La interacción entre celdas puede realizarse mediante carga eléctrica, magnetismo, vibración ( fonones a escalas cuánticas) o cualquier otro medio físicamente útil. Esto puede hacerse de varias maneras, de modo que no se necesiten cables entre los elementos. Esto difiere notablemente de los procesadores utilizados en la mayoría de las computadoras actuales ( diseños de von Neumann ), que se dividen en secciones con elementos que pueden comunicarse con elementos distantes mediante cables.

La regla 30 se sugirió originalmente como un posible cifrado de bloques para su uso en criptografía . Los autómatas celulares bidimensionales pueden utilizarse para construir un generador de números pseudoaleatorios . [ 86 ] Se han propuesto autómatas celulares para la criptografía de clave pública . La función unidireccional es la evolución de un CA finito 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 al diseño de códigos de corrección de errores . [ 87 ]

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

Arte y música generativos

Los autómatas celulares se han utilizado en la música generativa [ 88 ] y la composición musical evolutiva [ 89 ] y la generación procedural de terrenos en videojuegos. [ 90 ]

Generación de laberintos

Ciertos tipos de autómatas celulares pueden usarse para generar laberintos. [ 91 ] Dos autómatas celulares bien conocidos, Maze y Mazectric, tienen cadenas de reglas B3/S12345 y B3/S1234. [ 91 ] En el primero, esto significa que las células sobreviven de una generación a la siguiente si tienen al menos un vecino y como máximo cinco . En el segundo, esto significa que las células sobreviven si tienen de uno a cuatro vecinos. Si una célula tiene exactamente tres vecinos, nace. Es similar al Juego de la Vida de Conway en el sentido de que los patrones que no tienen una célula viva adyacente a 1, 4 o 5 otras células vivas en cualquier generación se comportarán de forma idéntica a él. [ 91 ] Sin embargo, para patrones grandes, se comporta de forma muy diferente a Life. [ 91 ]

Para un patrón inicial aleatorio, estos autómatas celulares generadores de laberintos evolucionarán hacia laberintos complejos con paredes bien definidas que delimitan corredores. Mazectric, que tiene la regla B3/S1234, tiende a generar corredores más largos y rectos en comparación con Maze, con la regla B3/S12345. [ 91 ] Dado que estas reglas de autómatas celulares son deterministas , cada laberinto generado está determinado de forma única por su patrón inicial aleatorio. Esto es una desventaja significativa, ya que los laberintos tienden a ser relativamente predecibles.

Al igual que algunos de los métodos basados ​​en la teoría de grafos descritos anteriormente, estos autómatas celulares suelen generar laberintos a partir de un único patrón inicial; por lo tanto, normalmente será relativamente fácil encontrar el camino a la celda de inicio, pero más difícil encontrar el camino a cualquier otro lugar.

Reglas específicas

Las reglas específicas de los autómatas celulares incluyen:

Véase también

Referencias

  1. ↑ Daniel Dennett (1995), La peligrosa idea de Darwin , Penguin Books, Londres, ISBN 978-0-14-016734-4, ISBN 0-14-016734-X
  2. 1 2 Wolfram, Stephen (1983). "Mecánica estadística de autómatas celulares" . Reviews of Modern Physics . 55 (3): 601– 644. Bibcode : 1983RvMP...55..601W . doi : 10.1103/RevModPhys.55.601 . Archivado del original el 21 de septiembre de 2013. Recuperado el 28 de febrero de 2011 .
  3. ↑ Toffoli, Tommaso; Margolus, Norman (1987). Cellular Automata Machines: A New Environment for Modeling . MIT Press. p. 27. ISBN  978-0-262-20060-8.
  4. ↑ Schiff, Joel L. (2011). Autómatas celulares: una visión discreta del mundo . Wiley & Sons, Inc. pág. 40. ISBN  978-1-118-03063-9.
  5. 1 2 3 4 Kier, Seybold, Cheng 2005 , pág. 15 
  6. 1 2 Bialynicki-Birula, Bialynicka-Birula 2004 , pág. 9 
  7. ↑ Schiff 2011 , pág. 41 
  8. ↑ Pickover, Clifford A. (2009). El libro de matemáticas: De Pitágoras a la dimensión 57, 250 hitos en la historia de las matemáticas . Sterling Publishing Company, Inc. pág. 406. ISBN  978-1-4027-5796-9.
  9. 1 2 Schiff 2011 , pág. 1 
  10. ↑ John von Neumann, "La teoría general y lógica de los autómatas", en LA Jeffress , ed., Mecanismos cerebrales en el comportamiento: el simposio Hixon, John Wiley & Sons, Nueva York, 1951, págs. 1-31.
  11. ↑ Kemeny, John G. (1955). "El hombre visto como una máquina". Sci. Am . 192 (4): 58– 67. Bibcode : 1955SciAm.192d..58K . doi : 10.1038/scientificamerican0455-58 .; Ciencia. Soy. 1955; 192:6 (erratas).
  12. ↑ Schiff 2011 , pág. 3 
  13. ↑ Ilachinski 2001 , pág. xxix 
  14. ↑ Bialynicki-Birula, Bialynicka-Birula 2004 , pág. 8 
  15. 1 2 Wolfram 2002 , pág. 876 
  16. ↑ von Neumann 1966
  17. 1 2 Wiener, N.; Rosenblueth, A. (1946). "La formulación matemática del problema de la conducción de impulsos en una red de elementos excitables conectados, específicamente en el músculo cardíaco". Arch. Inst. Cardiol. México . 16 (3): 205– 65. PMID 20245817 . 
  18. ↑ Letichevskii, AA; Reshodko, LV (1974). "La teoría de N. Wiener sobre la actividad de los medios excitables". Cibernética . 8 (5): 856– 864. doi : 10.1007/bf01068458 . S2CID 121306408 . 
  19. ↑ Davidenko, JM; Pertsov, AV; Salomonsz, R.; Baxter, W.; Jalife, J. (1992). "Ondas espirales estacionarias y en deriva de excitación en músculo cardíaco aislado". Nature . 355 ( 6358): 349– 351. Bibcode : 1992Natur.355..349D . doi : 10.1038/355349a0 . PMID 1731248. S2CID 4348759 .  
  20. ↑ Hedlund, GA (1969). "Endomorfismos y automorfismos del sistema dinámico de cambio". Math. Systems Theory . 3 (4): 320– 3751. doi : 10.1007/BF01691062 . S2CID 21803927 . 
  21. ↑ Schiff 2011 , pág. 182 
  22. ↑ Smith, Alvy Ray. "Compromisos de complejidad de los autómatas celulares" (PDF) . Archivado (PDF) del original el 27 de septiembre de 2015. Recuperado el 11 de febrero de 2018 .
  23. ↑ Smith, Alvy Ray. "Espacios celulares universales de computación simple" (PDF) . Archivado (PDF) del original el 14 de junio de 2018. Recuperado el 11 de febrero de 2018 .
  24. ↑ Smith, Alvy Ray. "Máquinas autorreproductoras simples no triviales" (PDF) . Archivado (PDF) del original el 27 de septiembre de 2015. Recuperado el 11 de febrero de 2018 .
  25. ↑ Smith, Alvy Ray. "Introducción y panorama general de la teoría de autómatas celulares o poliautómatas" (PDF) . Archivado (PDF) del original el 7 de agosto de 2015. Recuperado el 11 de febrero de 2018 .
  26. ↑ Gardner, Martin (1970). "Juegos matemáticos: Las fantásticas combinaciones del nuevo juego de solitario "la vida" de John Conway"Scientific American . 223 (4): 120– 123. doi : 10.1038/scientificamerican1070-120 . Archivado del original el 27 de agosto de 2013. Recuperado el 24 de agosto de 2011 .
  27. ↑ Paul Chapman. La computadora universal de la vida. http://www.igblan.free-online.co.uk/igblan/ca/ Archivado el 6 de septiembre de 2009 en Wayback Machine . Noviembre de 2002
  28. ↑ Wainwright 2010 , pág. 16 
  29. 1 2 3 4 5 Wolfram 2002 , pág. 880 
  30. ↑ Wolfram 2002 , pág. 881 
  31. ↑ Mitchell, Melanie (4 de octubre de 2002). "¿Es el Universo una computadora universal?". Science . 298 (5591): 65– 68. doi : 10.1126/science.1075073 . S2CID 122484855 . 
  32. 1 2 3 Ilachinsky 2001 , pág. 12 
  33. ↑ Ilachinsky 2001 , pág. 13 
  34. ↑ Wolfram 2002 , pág. 231 
  35. ↑ G. Cattaneo; E. Formenti; L. Margara (1998). «Caos topológico y CA» . En M. Delorme; J. Mazoyer (eds.). Autómatas celulares: un modelo paralelo . Saltador. pag. 239.ISBN​  978-0-7923-5493-2.
  36. ↑ Burton H. Voorhees (1996). Análisis computacional de autómatas celulares unidimensionales . World Scientific. pág. 8. ISBN  978-981-02-2221-5.
  37. ↑ Max Garzon (1995). Modelos de paralelismo masivo: análisis de autómatas celulares y redes neuronales . Springer. pág . 149. ISBN  978-3-540-56149-1.
  38. 1 2 Li, Wentian ; Packard, Norman (1990). "La estructura del espacio de reglas de los autómatas celulares elementales" (PDF) . Sistemas complejos . 4 : 281–297 . Archivado (PDF) del original el 25 de junio de 2016. Recuperado el 25 de enero de 2013 .
  39. ↑ Nicolis (1974). " Estructuras disipativas, catástrofes y formación de patrones: un análisis de bifurcación" (PDF) . PNAS . 71 (7): 2748– 2751. Bibcode : 1974PNAS...71.2748N . doi : 10.1073 /pnas.71.7.2748 . PMC 388547. PMID 16592170. Archivado (PDF) del original el 25 de junio de 2016. Recuperado el 25 de marzo de 2017 .  
  40. ^ Kari , Jarrko 1991 , pág. 379 
  41. ↑ Richardson, D. (1972). "Teselaciones con transformaciones locales" . J. Comput. Syst. Sci . 6 (5): 373– 388. doi : 10.1016/S0022-0000(72)80009-6 .
  42. ↑ Margenstern, Maurice (2007). Autómatas celulares en espacios hiperbólicos – Tomo I, Volumen 1. Archives contemporaines. p. 134. ISBN  978-2-84703-033-4.
  43. ↑ Schiff 2011 , pág. 103 
  44. ↑ Amoroso, Serafino; Patt, Yale N. (1972). "Procedimientos de decisión para la sobreyectividad e inyectividad de mapas paralelos para estructuras de teselación" . J. Comput. Syst. Sci . 6 (5): 448– 464. doi : 10.1016/s0022-0000(72)80013-8 .
  45. ↑ Sutner, Klaus (1991). "Grafos de De Bruijn y autómatas celulares lineales" (PDF) . Sistemas complejos . 5 : 19–30 . Archivado (PDF) del original el 14 de mayo de 2011. Recuperado el 7 de febrero de 2011 .
  46. ↑ Kari, Jarkko (1990). "La reversibilidad de los autómatas celulares 2D es indecidible". Physica D. 45 ( 1–3 ) : 379–385 . Bibcode : 1990PhyD...45..379K . doi : 10.1016/0167-2789(90)90195-U .
  47. ↑ Kari, Jarkko (1999). "Sobre la profundidad del circuito de los autómatas celulares estructuralmente reversibles". Fundamenta Informaticae . 38 : 93–107 . doi : 10.3233/FI-1999-381208 .
  48. ↑ Durand-Lose, Jérôme (2001). "Representación de autómatas celulares reversibles con autómatas celulares de bloques reversibles" . Matemáticas Discretas e Informática Teórica . AA : 145–154 . Archivado del original el 15 de mayo de 2011.
  49. ↑ Wolfram 2002 , pág. 60 
  50. 1 2 Ilachinski, Andrew (2001). Autómatas celulares: un universo discreto . World Scientific. págs. 44–45 . ISBN  978-981-238-183-5.
  51. ↑ La frase " autómata celular realista " se remonta al menos a Barral, Chaté y Manneville (1992) , quienes la usaron en un sentido más amplio para referirse a autómatas totalistas externos, no necesariamente de dos dimensiones. El significado más específico que se le da aquí se usó, por ejemplo, en varios capítulos de Adamatzky (2010) . Véase: Barral, Bernard; Chaté, Hugues; Manneville, Paul (1992). "Comportamientos colectivos en una familia de autómatas celulares de alta dimensión". Physics Letters A. 163 ( 4): 279– 285. Bibcode : 1992PhLA..163..279B . doi : 10.1016/0375-9601(92)91013-H .
  52. ↑ Eppstein 2010 , págs. 72–73 
  53. ↑ Jacob Aron. "Los primeros planeadores navegan por el universo siempre cambiante de Penrose" . New Scientist .
  54. ↑ Murray, JD (2003). Biología matemática (3.ª ed.). Nueva York: Springer. ISBN  0-387-95228-4.
  55. ↑ Pivato, M: "RealLife: El límite continuo de los autómatas celulares más grandes que la vida", Theoretical Computer Science , 372 (1), marzo de 2007, pp. 46–68
  56. ↑ Tomita, Kohji; Kurokawa, Haruhisa; Murata, Satoshi (2009). «Autómatas de reescritura de grafos como una extensión natural de los autómatas celulares». Redes adaptativas . Comprensión de sistemas complejos. págs. 291–309 . doi : 10.1007/978-3-642-01284-6_14 . ISBN  978-3-642-01283-9.
  57. ↑ 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 .  
  58. ↑ Weinberg, Steven (24 de octubre de 2002). "¿Es el universo una computadora?" . The New York Review of Books . 49 (16) . Recuperado el 12 de octubre de 2012 .
  59. ↑ Wentian Li; Norman Packard; Chris G Langton (1990). "Fenómenos de transición en el espacio de reglas de autómatas celulares". Physica D. 45 ( 1–3 ) : 77–94 . Bibcode : 1990PhyD...45...77L . CiteSeerX 10.1.1.15.2786 . doi : 10.1016/0167-2789(90)90175-O . 
  60. 1 2 3 Coombs, Stephen (15 de febrero de 2009), La geometría y pigmentación de las conchas marinas (PDF) , págs. 3–4 , archivado del original (PDF) el 7 de enero de 2013 , consultado el 2 de septiembre de 2012 
  61. ^ Cuevas, Erik; Ávila, Karla; Islas Toski, Miguel; Escobar, Héctor (2025). Modelos basados ​​en agentes con MATLAB . Morgan Kaufman. pag. 105.ISBN​  9780443240058.
  62. ↑ Berto, Francisco; Tagliabue, Jacopo (2023). «Autómatas celulares» . Enciclopedia de Filosofía de Stanford . Prensa de la Universidad de Stanford.
  63. ↑ Graw, Frederik; Perelson, Alan S. (septiembre de 2012). «Aspectos espaciales de la infección por VIH». En Ledzewicz, Urszula; Schättler, Heinz; Friedman, Avner; Kashdan, Eugene (eds.). Métodos y modelos matemáticos en biomedicina . Springer New York. pp. 3–31 . doi : 10.1007/978-1-4614-4178-6_1 . ISBN  9781461441786.
  64. ↑ Peak, West; Messinger, Mott (2004). "Evidencia de dinámicas colectivas complejas y computación distribuida emergente en plantas" . Actas de la Academia Nacional de Ciencias . 101 (4): 918– 922. Bibcode : 2004PNAS..101..918P . doi : 10.1073/pnas.0307811100 . PMC 327117. PMID 14732685 .  
  65. ↑ "Copia archivada" (PDF) . Archivado del original (PDF) el 25 de julio de 2010. Recuperado el 14 de septiembre de 2008 .{{cite web}}: CS1 mantenimiento: copia archivada como título ( enlace )
  66. ↑ Ilachinsky 2001 , pág. 275 
  67. ↑ Yves Bouligand (1986). "Fibroblastos, morfogénesis y autómatas celulares". Sistemas desordenados y organización biológica . págs. 374–375 . 
  68. ↑ Ilina, Olga; Gritsenko, Pavlo G.; Syga, Simon; Lippoldt, Jürgen; La Porta, Caterina AM; Chepizhko, Oleksandr; Grosser, Steffen; Vullings, Manon; Bakker, Gert-Jan; Starruß, Jörn; Bult, Peter (septiembre de 2020). "La adhesión célula-célula y el confinamiento de la matriz 3D determinan las transiciones de atasco en la invasión del cáncer de mama" . Nature Cell Biology . 22 (9): 1103– 1115. doi : 10.1038/s41556-020-0552-6 . ISSN 1465-7392 . PMC 7502685. PMID 32839548 .   
  69. ↑ Reher, David; Klink, Barbara; Deutsch, Andreas; Voss-Böhme, Anja (11 de agosto de 2017). "La heterogeneidad de la adhesión celular refuerza la diseminación de células tumorales: nuevas perspectivas a partir de un modelo matemático" . Biology Direct . 12 (1): 18. doi : 10.1186/s13062-017-0188-z . ISSN 1745-6150 . PMC 5553611. PMID 28800767 .   
  70. ^ Hatzikiro, H.; Basanta, D.; Simón, M.; Schaller, K.; Deutsch, A. (1 de marzo de 2012). "«Ir o crecer»: ¿la clave para la aparición de la invasión en la progresión tumoral? . Medicina Matemática y Biología . 29 (1): 49– 65. doi : 10.1093/imammb/dqq011 . ISSN 1477-8599 . PMID 20610469 . Archivado del original el 18 de octubre de 2021 . Recuperado el 21 de julio de 2021 .  
  71. ↑ AK Dewdney, La máquina de la mezcla hace olas, Scientific American, pág. 104, agosto de 1988.
  72. ↑ Gerhardt, M.; Schuster, H. (1989). "Un autómata celular que describe la formación de estructuras espacialmente ordenadas en sistemas químicos". Physica D. 36 ( 3): 209– 221. Bibcode : 1989PhyD...36..209G . doi : 10.1016/0167-2789(89)90081-x .
  73. ↑ Witten, TA; Sander, LM (9 de noviembre de 1981). "Agregación limitada por difusión, un fenómeno crítico cinético" . Physical Review Letters . 47 (19): 1400– 1403. Bibcode : 1981PhRvL..47.1400W . doi : 10.1103/PhysRevLett.47.1400 . Archivado del original el 26 de noviembre de 2024. Recuperado el 3 de febrero de 2025 .
  74. ↑ Woodruff, DP (13 de abril de 2015). "¿Cómo crece tu cristal? Un comentario sobre Burton, Cabrera y Frank (1951) 'El crecimiento de los cristales y la estructura de equilibrio de sus superficies'"." . Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences . 373 (2039) 20140230. Bibcode : 2015RSPTA.37340230W . doi : 10.1098/rsta.2014.0230 . PMC 4360084 . PMID 25750141 .  
  75. ↑ Goranova, D.; Rashkov, R.; Avdeev, G.; Tonchev, V. (1 de septiembre de 2016). "Electrodeposición de aleaciones de Ni-Cu a altas densidades de corriente: detalles de la distribución de elementos" . Journal of Materials Science . 51 (18): 8663– 8673. Bibcode : 2016JMatS..51.8663G . doi : 10.1007/s10853-016-0126-y . ISSN 1573-4803 . 
  76. ↑ Sethna, James P. (2008). Mecánica estadística: entropía, parámetros de orden y complejidad . Oxford University Press . ISBN 978-0-198-56677-9. OCLC 845714772 . Archivado del original el 7 de junio de 2021 . Consultado el 19 de agosto de 2025 . 
  77. ↑ Kardar, Mehran (2007). Física estadística de campos . Cambridge University Press . ISBN 978-0-521-87341-3OCLC 920137477​​ 
  78. ↑ Cappelli, Andrea; Zuber, Jean-Bernard (2010). "Clasificación ADE de teorías de campos conformes" . Scholarpedia . 5 (4) 10314. arXiv : 0911.3242 . Bibcode : 2010SchpJ...510314C . doi : 10.4249/scholarpedia.10314 . S2CID 18207779 . 
  79. 1 2 F. Krzyżewski, M. Załuska-Kotur, A. Krasteva, H. Popova y V. Tonchev, «Agrupación de escalones y formación de macroescalones en un modelo a escala atómica 1D del crecimiento inestable de cristales vicinales», Journal of Crystal Growth 474 , 135 (2017). DOI
  80. ↑ O. Toktarbaiuly et al., "Agrupamiento de escalones con ambas direcciones de la corriente: superficies W(110) vecinales frente a un modelo a escala atómica," Phys. Rev. B 97 , 035436 (2018). DOI
  81. 1 2 F. Krzyżewski, M. Załuska-Kotur, A. Krasteva, H. Popova y V. Tonchev, «Escalado y estabilidad dinámica de superficies vicinales modelo», Crystal Growth & Design 19 , 821 (2019). DOI
  82. ↑ H. Popova, F. Krzyżewski, MA Załuska-Kotur y V. Tonchev, «Cuantificación del efecto de la exclusión de escalones en superficies vicinales dinámicamente inestables: agrupamiento de escalones sin formación de macroescalones», Crystal Growth & Design 20 , 7246 (2020). DOI
  83. ^ M. Załuska-Kotur, H. Popova y V. Tonchev, "Haces de pasos, nanocables y otras 'criaturas' vecinas: efecto Ehrlich-Schwoebel por autómatas celulares", Crystals 11 , 1135 (2021). DOI
  84. ↑ AV Redkov, "Ciencia de datos de la cristalización in silico", Acta Materialia 287 , 120762 (2025). DOI
  85. ↑ Muhtaroglu, Ali (agosto de 1996). "4.1 Procesador de autómatas celulares (CAP)". Sistemas basados ​​en procesadores de autómatas celulares para la comparación de secuencias genéticas y la búsqueda en bases de datos . Universidad de Cornell. págs. 62–74 . 
  86. ↑ Tomassini, M.; Sipper, M.; Perrenoud, M. (2000). "Sobre la generación de números aleatorios de alta calidad mediante autómatas celulares bidimensionales" . IEEE Transactions on Computers . 49 (10): 1146– 1151. Bibcode : 2000ITCmp..49.1146T . doi : 10.1109/12.888056 . S2CID 10139169. Archivado del original el 24 de junio de 2021. Recuperado el 17 de junio de 2025 . 
  87. ↑ Chowdhury, D. Roy; Basu, S.; Gupta, I. Sen; Chaudhuri, P. Pal (junio de 1994). "Diseño de CAECC: código corrector de errores basado en autómatas celulares". IEEE Transactions on Computers . 43 (6): 759– 764. Bibcode : 1994ITCmp..43..759C . doi : 10.1109/12.286310 .
  88. ↑ Burraston, Dave y Ernest Edmonds. " Autómatas celulares en la música electrónica generativa y el arte sonoro: una revisión histórica y técnica. Archivado el 25 de noviembre de 2020 en Wayback Machine ". Digital Creativity 16.3 (2005): 165-185.
  89. ↑ Miranda, Eduardo Reck. " Música de autómatas celulares en evolución: De la síntesis de sonido a la composición ". Actas del Taller de 2001 sobre Modelos de Vida Artificial para Aplicaciones Musicales. 2001.
  90. ↑ Ashlock, Daniel; Kreitzer, Matthew (2020). «Evolución de mapas de nivel basados ​​en autómatas celulares diversos» . Actas de la 6.ª Conferencia Internacional de Ingeniería de Software para Aplicaciones de Defensa . Avances en Sistemas Inteligentes y Computación. Vol. 925. págs. 10–23 . doi : 10.1007/978-3-030-14687-0_2 . ISBN   978-3-030-14686-3. S2CID 85562837 . Archivado del original el 8 de abril de 2022 . Recuperado el 7 de junio de 2021 . 
  91. ^ Nathaniel Johnston ;​ ​et al. (21 de agosto de 2010). "Laberinto" . VidaWiki . Consultado el 22 de abril de 2025 . 

Obras citadas

  • Adamatzky, Andrés , ed. (2010). Juego de Autómatas Celulares de la Vida . Saltador. ISBN 978-1-84996-216-2.
  • Bialynicki-Birula, Iwo; Bialynicka-Birula, Iwona (2004). Modelando la realidad: cómo las computadoras reflejan la vida . Oxford University Press . ISBN 978-0-19-853100-5.
  • Chopard, Bastien; Droz, Michel (2005). Modelado de sistemas físicos mediante autómatas celulares . Cambridge University Press . ISBN 978-0-521-46168-9.
  • Eppstein, David. "Crecimiento y decadencia en autometacelulares similares a la vida". En Adamatzky (2010) .
  • Gutowitz, Howard, ed. (1991). Autómatas celulares: teoría y experimento . Prensa del MIT . ISBN 978-0-262-57086-2.
  • Ilachinski, Andrew (2001). Autómatas celulares: un universo discreto . World Scientific . ISBN 978-981-238-183-5.
  • Kier, Lemont B.; Seybold, Paul G.; Cheng, Chao-Kun (2005). Modelado de sistemas químicos mediante autómatas celulares . Saltador. ISBN 978-1-4020-3657-6.
  • von Neumann, John (1966). Burks, Arthur W. (ed.). Teoría de los autómatas autorreproductores . Urbana: University of Illinois Press .
  • Wainwright, Robert. "El juego de la vida de Conway: primeros recuerdos personales". En Adamatzky (2010) .
  • Wolfram, Stephen (2002). Un nuevo tipo de ciencia . Wolfram Media . ISBN 978-1-57955-008-0.

Lecturas adicionales

  • Berto, Francisco; Tagliabue, Jacopo. «Autómatas celulares» . En Zalta, Edward N. (ed.). Enciclopedia de Filosofía de Stanford . ISSN 1095-5054 . OCLC 429049174 .  
  • Crutchfeld, James P.; Mitchell, Melanie; Das, Rajarshi (2002). «El diseño evolutivo de la computación colectiva en autómatas celulares». En Crutchfield, JP; Schuster, PK (eds.). Dinámica evolutiva: Explorando la interacción entre selección, neutralidad, accidente y función . Nueva York: Oxford University Press.
  • Kroc, Jiří; Jiménez-Morales, Francisco; Guisado, José Luis; Lemos, María Carmen; Tkáč, Jakub (diciembre de 2019). "Construcción de modelos eficientes de autómatas celulares computacionales de sistemas complejos: antecedentes, aplicaciones, resultados, software y patologías" . Advances in Complex Systems . 22 (5): 1950013 (38 páginas). doi : 10.1142/S0219525919500139 . S2CID 212988726 . 
  • Mitchell, Melanie; Crutchfeld, James P.; Das, Rajarshi (1996). Evolución de autómatas celulares con algoritmos genéticos: una revisión de trabajos recientes . Actas de la Primera Conferencia Internacional sobre Computación Evolutiva y sus Aplicaciones (EvCA'96). Moscú, Rusia: Academia Rusa de Ciencias.
  • Turing, AM (1952). "The Chemical Basis of Morphogenesis". Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences . B237 (641): 37– 72. Bibcode : 1952RSPTB.237...37T . doi : 10.1098/rstb.1952.0012 .Propone la reacción-difusión, un tipo de autómata continuo.
  • Mirek's Cellebration : plataforma que alberga el software gratuito "MCell", un explorador de autómatas celulares. El software admite una gran cantidad de reglas 1D y 2D. El sitio ofrece un extenso léxico de reglas y numerosas galerías de imágenes con ejemplos. El código fuente (JavaScript) está disponible.
  • Golly es compatible con los sistemas de autómatas celulares de von Neumann, Nobili, GOL y muchos otros. Desarrollado por Tomas Rokicki y Andrew Trevorrow, este es el único simulador disponible actualmente que puede demostrar la autorreplicación de tipo von Neumann.
  • Wolfram Atlas – Un atlas de varios tipos de autómatas celulares unidimensionales.
  • Vida en Conway
  • Preguntas frecuentes sobre autómatas celulares del grupo de noticias comp.theory.cell-automata
  • "Encuesta vecinal" (incluye un análisis de las cuadrículas triangulares y las áreas de clasificación vecinal más grandes).
  • El cuaderno de autómatas celulares de Cosma Shalizi contiene una extensa lista de material de referencia académico y profesional.
Obtenido de " https://en.wikipedia.org/w/index.php?title=Cellular_automaton&oldid=1356961404 "