Autómatas celulares (teoría)

De Bestiario del Hypogripho
Una imagen de Conway's Game of Life una regla para autómatas celulares en dos dimensiones.

Este artículo tiene contenido abordado desde la perspectiva de la "vida real".   Este artículo tiene elementos que forman parte del Omniverso de los autómatas celulares.     Este artículo se compone de contenidos transcritos o recopilados por Avengium (Ángel Montero Lamas).  Este artículo está ilustrado con imágenes de Wikimedia Commons, ninguna otra persona, ningún autor adicional y nadie más.  Este artículo tiene bibliografía real que sustenta su contenido en todo o en parte.  Este artículo tiene una dificultad intraficcional mínima (magnitud 1). Debería resultar accesible para el público en general. 

Un autómata celular (abreviado AC, en inglés CA) es un modelo matemático y computacional para un sistema dinámico que evoluciona en pasos discretos. Es estudiado en la teoría de autómatas.[r 1] Los autómatas celulares han encontrado aplicación en varias áreas, incluyendo física, biología teórica y modelado de microestructuras.

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.

Elementos básicos[editar]

Los elementos básicos de un autómata celular son:

  • Un espacio regular: Ya sea una línea, un plano de dos dimensiones o un espacio n-dimensional. Cada división homogénea de este espacio es llamada célula. Esto se hace mediante un retículo, rejilla o cuadrícula.
  • Conjunto de Estados: Es finito y cada elemento o célula del espacio toma un valor de este conjunto de "estados", tales como "encendido" y "apagado". También se denomina alfabeto. Estos valores pueden expresarse numéricamente, descriptivamente o con colores según se prefiera.
  • Configuración Inicial: Es la asignación inicial de un estado a cada una de las células del espacio.
  • Vecindades: Define el conjunto de células que se consideran adyacentes a una dada, así como la posición relativa respecto a ella. Cuando el espacio es uniforme, la vecindad de cada célula es isomorfa (es decir, que tiene el mismo aspecto).
  • Función de Transición Local: Es la regla de evolución que determina el comportamiento del A.C. Se calcula a partir del estado de la célula y su vecindad. Define cómo debe cambiar de estado cada célula dependiendo de su estado anterior y de los estados anteriores de su vecindad. Suele darse como una expresión algebraica o un grupo de ecuaciones.

La clasificación de Wolfram para los autómatas celulares es:

  • Clase I: Lleva a un estado homogéneo perdiendo la aleatoriedad del estado inicial.
  • Clase II: Se generan estructuras cíclicas, separadas y simples. Los cambios en la configuración inicial sólo afectan una región finita de células cercanas.
  • Clase III: Casi todos los patrones iniciales evolucionan de forma caótica. Los cambios en la configuración inicial tienden a propagarse indefinidamente.
  • Clase IV: Se producen estructuras complejas no explicadas por las clases anteriores. Tienen combinación de patrones cíclicos y comportamiento aleatorio.

Condiciones de frontera[editar]

Un AC con condición de frontera periódica. En un espacio de dos dimensiones esto se desarrolla como un toroide. En la imagen, un glider gun (disparador de planeadores) dispara una corriente de planeadores que finalmente envuelve y destruye el arma.
Un AC con dos valores, "blanco" para 0, y "rojo" para 1. Se puede ver como un patrón llamado "glider" o planeador actúa en una rejilla con condiciones de frontera periódicas.

Por definición, un A.C. consiste en una retícula infinita de números enteros. Sin embargo, para cuestiones prácticas (como en modelos de sistemas físicos llevados a cabo en ordenadores de memoria finita), se requiere tomar ciertas consideraciones a la hora de implementar un A.C. Por ello, la definición original se modifica para dar cabida a retículas finitas en las que las células del A.C. interactúen. Esto conlleva la consideración extra de lo que debe suceder con aquellas células que se encuentren en los bordes de la retícula. A la implementación de una o varias consideraciones específicas se le conoce como condición de frontera.

Dentro del ámbito de los A.C., se pueden implementar numerosas condiciones de frontera, en función de lo que el problema real requiera para su modelado. Por ejemplo:

  • Frontera abierta. Se considera que fuera de la cuadrícula residen células, todas con un valor fijo. En el caso particular del juego de la vida de Conway y de otros A.C. con dos estados en su conjunto , una frontera se dice fría si las células fuera de la frontera se consideran muertas, y caliente si se consideran vivas.
  • Frontera periódica. Se considera a la cuadrícula como si sus extremos se tocaran. En una cuadrícula de dimensión 1, esto puede visualizarse en dos dimensiones como una circunferencia. En dimensión 2, la cuadrícula podría visualizarse en tres dimensiones como un toroide. Otra ventaja de la frontera periódica, es que es fácilmente programable usando funciones de aritmética modular. Por ejemplo, en un autómata celular unidimensional, la vecindad de una celda xit es {xi−1t−1, xit−1 , xi+1t−1} , donde t es el paso de tiempo (vertical) e i es el índice (horizontal) en una generación.
  • Frontera reflectora. Se considera que las células fuera de la cuadrícula "reflejan" los valores de aquellas dentro de la cuadrícula. Así, una célula que estuviera junto al borde de la cuadrícula (fuera de ella) tomaría como valor el de la célula que esté junto al borde de la cuadrícula, dentro de ella.
  • Sin frontera. Haciendo uso de implementaciones que hagan crecer dinámicamente el uso de memoria de la cuadrícula implementada, se puede asumir que cada vez que las células deben interactuar con células fuera de la cuadrícula, esta se hace más grande para dar cabida a estas interacciones. Obviamente, existe un límite (impuesto por la memoria disponible) para esta condición. Es muy importante no confundir esta condición de frontera con la definición original de A.C. cuya cuadrícula es inicialmente infinita. En el caso de un A.C. sin frontera, la cuadrícula comienza con un tamaño definido y finito, y conforme se requiera va creciendo en el tiempo, lo cual no lo hace necesariamente un modelo más cercano a la realidad, pues si se inicializara la cuadrícula aleatoriamente, con esta condición sólo se pueden inicializar las células dentro de la cuadrícula inicial finita, mientras que en el caso de la definición original, en teoría todas las células de la cuadrícula infinita deberían ser inicializadas.

Variaciones[editar]

Un oscilador de 4 etapas en una rejilla triangular (regla S456 B48).

Los A.C. pueden variar en cualquiera de sus características básicas, derivando en autómatas celulares no estándar.

Sistema dinámico que evoluciona en pasos discretos. En un espacio regular, con una serie de estados, una configuración inicial y unas vecindades. La evolución del sistema es definida por una función de transición.

un A.C. estándar tiene una cuadrícula donde se asume que las células son cuadrados; es decir, que la retícula tiene una geometría cuadrada. Se puede variar el A.C. para presentar una geometría triangular o hexagonal (en A.C. de 2 dimensiones, el cuadrado, el triángulo y el hexágono son las únicas figuras geométricas que llenan el plano).

También puede variarse:

  • el conjunto de estados que cada célula puede tomar, por ejemplo haciendo que sea de tres o más estados.
  • la función de transición de forma que ya no sea homogénea, utilizar elementos estocásticos (aleatoriedad) en (lo que se conoce como A.C. probabilístico).
  • variar las vecindades de cada célula, por ejemplo con una vecindad reducida o extendida.
  • los números enteros y discretos por valores continuos y números de coma flotante, como en SmoothLife.

Autómatas celulares más simples[editar]

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 vecinas forman una vecindad de 3 celdas, por lo que hay 23 = 8 patrones posibles para una vecindad. Una regla consiste en decidir, para cada patrón, si la celda será un 1 o un 0 en la próxima generación. Hay entonces 28 = 256 reglas posibles.[r 2]

Una animación de la forma en que las reglas de un autómata celular 1D determinan la próxima generación.

Estos 256 autómatas celulares generalmente se denominan por su Código de Wolfram, una convención de nombres 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 regla 30 y regla 110 son ​​particularmente interesantes. Las siguientes imágenes muestran el historial de estad dos reglas 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 el 0 y negro para el 1.

Regla 30

autómata celular Regla 30

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 Regla 110

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 de Conway, 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 transcurso del desarrollo de su libro A New Kind of Science, como asistente de investigación de Wolfram en 1994, Matthew Cook demostró que algunas de estas estructuras eran lo suficientemente ricas como para sustentar 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 de 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.[r 3] En 2004, la demostración de Cook finalmente se publicó en la revista de Wolfram Complex Systems (Vol. 15, No. 1), más de diez años después de que a Cook se le ocurrió. La regla 110 ha sido la base de algunas de las máquinas de Turing universales más pequeñas.[r 4]

Autómatas celulares de dos dimensiones[editar]

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

Una forma de simular un autómata celular bidimensional es con una hoja infinita de papel cuadriculado junto con un conjunto de reglas a seguir por las células. Cada cuadrado del papel es una "celda" y cada celda tiene dos estados posibles, blanco y negro. El "vecindario" de una celda son las celdas cercanas, generalmente adyacentes. Los dos tipos de vecindades más comunes son la vecindad de von Neumann que consta de las cuatro celdas ortogonales adyacentes.[r 5] y la vecindad de Moore que incluye la vecindad de von Neumann así como las cuatro celdas adyacentes en diagonal[r 6]. Para una celda concreta y su vecindad de Moore, hay 512 (= 29) 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.

Los autómatas posibles en Conway's Game of Life funcionan todos con vecindad de Moore. Otro tipo de vecindad común es la vecindad de von Neumann extendida, que incluye las dos celdas más cercanas en cada dirección ortogonal, para un total de ocho.[r 7] La ecuación general para tal sistema de reglas es kks, 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.[r 8] Así, en el sistema bidimensional con vecindad de Moore, el número total de autómatas posibles sería 229< /sup>, o 1.34 x10154.

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.[r 9] 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.

Clasificación[editar]

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.[r 10]
  • 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 desaparecer, pero queda algo. Los cambios locales al patrón inicial tienden a permanecer locales.[r 11]
  • 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.[r 12]
  • 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.[r 13] 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 ser Turing completos y con capacidad 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 algunas características de una clase y algunas de otra."[r 14] La clasificación de Wolfram se ha emparejado empíricamente con una agrupación de las longitudes comprimidas de las salidas de los autómatas celulares.[r 15]

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 se probó indecidible.[r 16][r 17][r 18] La clase 2 de Wolfram se puede dividir en dos subgrupos de reglas estables (de punto fijo) y oscilantes (periódicas).[r 19]

La idea de que hay 4 clases de sistemas dinámicos provino 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 espacialmente/temporalmente uniformes,
  3. sistemas caóticos, y
  4. sistemas complejos lejos del equilibrio con estructura disipativa.

Para esto ultimo vease la figura 1 en el artículo de Nicolis (estudiante de Prigogine).[r 20]

Reversibles[editar]

Un autómata celular es reversible si, por cada configuración actual del autómata celular, existe exactamente una configuración pasada o preimagen.[r 21] 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.[r 22] 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 una consecuencia del teorema de Curtis–Hedlund–Lyndon, una caracterización topológica de los autómatas celulares.[r 23][r 24] Para los autómatas celulares en los que no todas las configuraciones tienen preimagen, las configuraciones sin preimagen se denominan patrones Jardín del Edén.[r 25]

Para autómatas celulares unidimensionales existen algoritmos conocidos para decidir si una regla es reversible o irreversible.[r 26][r 27] 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 mosaico de los Azulejos Wang.[r 28]

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. Tales 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 dichos autómatas no satisfacen estrictamente la definición dada anteriormente, se puede demostrar que pueden ser emulados por autómatas celulares convencionales con vecindades y números de estados suficientemente grandes y, por lo tanto, pueden 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 de bloque. [r 29][r 30]

Totalistas[editar]

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 momento t − 1.[r 31][r 32] Si el estado de la celda en el momento 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 exterior.[r 33]

El juego de la vida de Conway es un ejemplo de un autómata celular totalista exterior con valores de estado 0 y 1 para las células. Los autómatas celulares totalistas exteriores con la misma estructura de vecindad de Moore que Life (B3/S23) a veces se denominan autómatas celulares símiles de vida.[r 34][r 35]

Autómatas relacionados[editar]

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

Un autómata celular basado en celdas hexagonales en lugar de cuadrados (regla B34/S2).

Una variación es usando algo que no sea una cuadrícula rectangular (cúbica, etc.). Por ejemplo, si un plano está cubierto por un Teselado hexagonal, 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 teselados de Penrose.[r 36]

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 momento t, las probabilidades de que la celda central haga la transición a cada estado posible en el momento t+ 1. A veces se usa una regla más simple; por ejemplo: "La regla es Life (B3/S23), pero en cada paso de tiempo hay una probabilidad del 0,001 % de que cada celda cambie al color opuesto".

La vecindad 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 celulares continuos. Estos son como autómatas celulares totalistas, pero en lugar de que la regla y los estados sean discretos (por ejemplo una tabla, usando los estados {0,1,2}), se usan funciones continuas y los estados se vuelven continuos (usualmente valores en Intervalo unidad como [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.[r 37] Cuando estos se aproximan mediante autómatas celulares, a menudo producen patrones similares. MacLennan [r 38] 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.[r 39]

Los autómatas de reescritura de grafos son extensiones de autómatas celulares basados ​​en sistemas de reescritura de grafoss.[r 40]

Espacio de reglas[editar]

Una regla para un autómata celular elemental se especifica mediante 8 bits. 28 = 256 reglas posibles. Si pensamos que cada regla tiene una ubicación física y que están puestas regularmente en función de sus valores y relación, las reglas para autómatas celulares elementales se asientan en los vértices de un hipercubo de 8 dimensiones. Una dimensión para cada bit que puede variar. 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 25 = 32 bits, y el espacio de reglas del autómata celular es un hipercubo 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, a otro vértice, que representa otra regla, a lo largo del borde del hipercubo. Esta distancia de regla a regla también se denomina 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. 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 en la cadena de 32 bits para reglas elementales para las reglas del vecino más próximo). Poner 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.[r 41]

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

Aplicaciones[editar]

El caparazón de Conus textile muestra un patrón con un aspecto similar a autómatas celulares de una dimensión.

Los autómatas celulares pueden ser usados para modelar numerosos sistemas físicos que se caractericen por un gran número de componentes homogéneos y que interactúen localmente entre sí. Cualquier sistema con los conceptos de "vecindad", "estados de los componentes" y "función de transición" es candidato para ser modelado por un A.C.

  • Modelado del flujo de tráfico y de peatones.
  • Modelado de fluidos (gases o líquidos).
  • Modelado de la evolución de células o virus como el VIH.
  • Modelado de procesos de filtración y ósmosis.

Reglas notables[editar]

Una dimensión[editar]

Dos dimensiones[editar]

Véase también[editar]

Referencias[editar]

Las Referencias aluden a las relaciones de un artículo con la "vida real".
  1. Wolfram, Esteban (1983). «Mecánica estadística de autómatas celulares». Reseñas de física moderna 55 (3): 601-644. Bibcode:1983RvMP...55..601W. doi:10.1103/RevModPhys.55.601. Archivado desde el original el 21 de septiembre de 2013. Consultado el 28 de febrero de 2011. 
  2. Plantilla:Harvnb
  3. Giles, Jim (2002). «What Kind of Science is This?». Nature 417 (6886): 216-218. Bibcode:2002Natur.417..216G. PMID 12015565. S2CID 10636328. doi:10.1038/417216a. 
  4. Weinberg, Steven (24 de octubre de 2002). «¿Es el universo una computadora?». The New York Review of Books. Consultado el 12 de octubre de 2012. 
  5. Plantilla:Harvnb
  6. Plantilla:Harvnb
  7. Plantilla:Harvnb
  8. Plantilla:Harvnb
  9. Plantilla:Harvnb
  10. Plantilla:Harvnb
  11. Plantilla:Harvnb
  12. Plantilla:Harvnb
  13. Plantilla:Harvnb
  14. Plantilla:Harvnb
  15. Zenil, Hector (2010). «Investigación basada en la compresión de las propiedades dinámicas de los autómatas celulares y otros sistemas». Complex Systems 19 (1): 1-28. S2CID 15364755. doi:10.25088/ComplexSystems.19.1.1. 
  16. G. Cattaneo; E. Formenti; L. Margara (1998). «Caos topológico y CA». En M. Delorme; J. Mazoyer, eds. Autómatas celulares: un modelo paralelo. Springer. p. 239. ISBN 978-0-7923-5493 -2. 
  17. Burton H. Voorhees (1996). books?id=WcZTQHPrG68C&pg=PA8 Análisis computacional de autómatas celulares unidimensionales. World Scientific. p. 8. ISBN 978-981-02-2221-5. 
  18. Max Garzon (1995). Springer, ed. Modelos de paralelismo masivo: análisis de autómatas celulares y redes neuronales. p. 149. ISBN 978-3-540-56149-1. 
  19. Li, Wentian; Packard, Norman (1990). «La estructura del espacio de reglas de los autómatas celulares elementales». Sistemas complejos 4: 281-297. Consultado el 25 de enero de 2013. 
  20. Nicolis (1974). «Estructuras disipativas, catástrofes y formación de patrones: un análisis de bifurcación». PNAS 71 (7): 2748-2751. Bibcode:1974PNAS...71.2748N. PMC 388547. PMID 16592170. doi:10.1073/pnas.71.7.2748. Consultado el 25 de marzo de 2017. 
  21. Plantilla:Harvnb
  22. Plantilla:Harvnb
  23. Richardson, D. (1972). «Teselados con transformaciones locales». Journal of computer sist. Sci. 6 (5): 373-388. doi:10.1016/S0022-0000(72)80009-6. 
  24. Margenstern, Maurice (2007). Cellular Automata in Hyperbolic Spaces – Tome I, Volume 1. Archives contemporaines. p. 134. ISBN 978-2-84703-033-4. 
  25. Plantilla:Harvnb
  26. Amorosos, Serafín; Patt, Yale N. (1972). «Procedimientos de decisión para sobreyectividad e inyectividad de mapas paralelos para estructuras de teselación». J. Cómputo. sist. ciencia 6 (5): 448-464. doi:10.1016/s0022-0000(72)80013-8. 
  27. Sutner, Klaus (1991). «De Bruijn Graphs and Linear Cellular Automata». Complex Systems 5: 19-30. 
  28. Kari, Jarkko (1990). «Reversibilidad de autómatas celulares 2D es indecidible». Physica D 45 (1–3): 379-385. Bibcode:..45..379K 1990PhyD. ..45..379K. doi:10.1016/0167-2789(90)90195-U. 
  29. Kari, Jarkko (1999). «On the circuit depth of structurally reversible cellular automata». Fundamenta Informaticae 38: 93-107. doi:10.3233/FI-1999-381208. 
  30. Durand-Lose, Jérôme (2001). www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/download/264/855 «Representing autómatas celulares reversibles con autómatas celulares de bloque reversibles». Matemáticas Discretas y Ciencias de la Computación Teórica. AA: 145-154. Archivado desde el original el 15 de mayo de 2011. 
  31. Plantilla:Harvnb
  32. Ilachinski, Andrew (2001). Cellular automata: a discrete un universe. World Scientific. pp. 44-45. ISBN 978-981-238-183-5. 
  33. Ilachinski, Andrew (2001). Cellular automata: a discrete universe. World Scientific. p. 44–45. ISBN 978-981-238-183-5. 
  34. La frase "life-like cellular automata" se remonta al menos a Barral, Chaté y Manneville (1992), quien la usó en un sentido más amplio para referirse a autómatas totalistas exteriores, no necesariamente de dos dimensiones. Se utilizó el significado más específico que se da aquí, por ejemplo en varios capítulos de Adamatzky (2010). Ver: Barral, Bernard; Chaté, Hugues; Manneville, Paul (1992). «Collective behaviors in a family of high-dimensional cellular automata». Physics Letters A 163 (4): 279-285. Bibcode:1992PhLA..163..279B. doi:10.1016/0375-9601(92)91013-H. 
  35. Plantilla:Harvnb
  36. Jacob Aron. «First gliders navigate ever-changing Penrose universe». New Scientist. 
  37. Murray, J. D. (2003). Biología matemática (3rd edición). Nueva York: Springer. ISBN 0-387-95228-4. 
  38. [1]
  39. Pivato, M: "RealLife: The continuum limit of Larger than Life cellular automata", Theoretical Computer Science , 372 (1), marzo de 2007, págs. 46–68
  40. Tomita, Kohji; Kurokawa, Haruhisa; Murata, Satoshi (2009). «Autómatas de reescritura de gráficos como una extensión natural de los autómatas celulares». Redes adaptativas. Comprender los sistemas complejos. pp. 291-309. ISBN 978-3 -642-01283-9. doi:10.1007/978-3-642-01284-6_14. 
  41. Li, Wentian; Packard, Norman (1990). «The structure of the elementary cellular automata rule space». Complex Systems 4: 281-297. Consultado el 25 January 2013. 
  42. Wentian Li; Norman Packard; Chris G Langton (1990). «Transition phenomena in cellular automata rule space». Physica D 45 (1–3): 77-94. Bibcode:1990PhyD...45...77L. doi:10.1016/0167-2789(90)90175-O. 

Enlaces externos[editar]

  • Wikimedia Commons alberga una galería multimedia sobre Autómatas celulares.
  • Mirek's Cellebration: Hogar del software gratuito de exploración de autómatas celulares MCell y MJCell y bibliotecas de reglas. El software admite una gran cantidad de reglas 1D y 2D. El sitio proporciona un extenso léxico de reglas y muchas galerías de imágenes cargadas con ejemplos de reglas. MCell es una aplicación de Windows, mientras que MJCell es un subprograma de Java. El código fuente está disponible.
  • Modern Cellular Automata: Exhibiciones interactivas fáciles de usar de autómatas celulares 2D en vivo y en color, con la tecnología del subprograma Java. Se incluyen exhibiciones de reglas tradicionales, reversibles, hexagonales, de múltiples pasos, generadoras de fractales y generadoras de patrones. Miles de reglas se proporcionan para su visualización. Hay software gratuito disponible.
  • Self-replication loops in Cellular Space: Exhibiciones potenciadas por applet de Java de bucles de autorreplicación.
  • A collection of over 10 different cellular automata applets en el laboratorio virtual de la Universidad de Monash.
  • Golly Programa multiplataforma que admite von Neumann, Nobili, GOL y muchos otros sistemas de autómatas celulares. Desarrollado por Tomas Rokicki y Andrew Trevorrow. Este es el único simulador actualmente disponible que puede demostrar la autorreplicación de tipo von Neumann.
  • Fourier Life: Una colección de reglas que demuestran patrones autorreplicantes que emergen espontáneamente de un campo de celdas aleatorias. La mayoría de las reglas se encontraron usando un algoritmo que usa una Transformada de Fourier para detectar la autorreplicación.
  • Wolfram Atlas – Un atlas de varios tipos de autómatas celulares unidimensionales.
  • Conway Life: Página de la comunidad de entusiastas de los autómatas celulares. En especifico de Conway's Game of Life.
  • First replicating creature spawned in life simulator
  • The Mathematics of the Models of Reference, con un tutorial general sobre AC, subprograma interactivo, código gratuito y recursos sobre AC como modelo de física fundamental.
  • Fourmilab Cellular Automata Laboratory
  • Busy Boxes, Un autómata celular 3-D, reversible, de arquitectura SALT.
  • Cellular Automata Repository Investigadores de AC, enlaces históricos, software libre, libros y más.
  • Cellular Automata in 256 Rules Una visualización interactiva de una sola hoja de las 256 reglas elementales (de una sola dimensión).
  • Petri -- a Go cellular automata framework

⚜️[editar]

0
Avatar creador genérico W240.png
Este artículo utiliza contenido de Wikipedia que se publica bajo una licencia CC BY-SA, CC-BY-SA.svg.
Ver contribuidores de Autómata celular
Avatar creador genérico W240.png
Este artículo utiliza contenido de Wikipedia que se publica bajo una licencia CC BY-SA, CC-BY-SA.svg.
Ver contribuidores de Cellular_automaton (en inglés)
 Avatar Avengium.png  Artículo transcrito por Avengium
Por favor, consulta rigurosamente las fuentes antes de cambiar o añadir algo a las transcripciones.
Icon libro 1.png