Autómata celular
Un autómata celular (A.C.) es un modelo matemático y computacional para un sistema dinámico que evoluciona en pasos discretos. Es adecuado para modelar sistemas naturales que puedan ser descritos como una colección masiva de objetos simples que interactúen localmente unos con otros.
Son sistemas descubiertos dentro del campo de la física computacional por John von Neumann en la década de 1950. La teoría de los autómatas celulares se inicia con su precursor John von Neumann a finales de la década de 1940 con su libro Theory of Self-reproducing Automata (editado y completado por A. W. Burks).
Aunque John von Neumann puso en práctica los AA.CC., estos fueron concebidos en los años 40 por Konrad Zuse y Stanislaw Ulam. Zuse pensó en los “espacios de cómputo” (computing spaces), como modelos discretos de sistemas físicos. Las contribuciones de Ulam vinieron al final de los 40, poco después de haber inventado con Nicholas Metropolis el Método de Montecarlo.
No existe una definición formal y matemática aceptada de autómata celular; sin embargo, se puede describir a un A.C. como una tupla, es decir, un conjunto ordenado de objetos caracterizado por los siguientes componentes:
Por definición, un A.C. consiste en una retícula infinita de 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:
Los A.C. pueden variar en alguna de las características antes mencionadas, derivando en autómatas celulares no estándar.
Por ejemplo, un A.C. estándar tiene una cuadrícula donde se asume que las células son cuadros; es decir, que la retícula tiene una geometría cuadrada. Esto no es necesariamente un requisito, y 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, 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, etc.
La historia de los autómatas celulares puede ser clasificada en tres etapas asociadas a los nombres de los científicos que en cada momento marcaron un punto de inflexión en el desarrollo de la teoría: la era de Von Neumann, la era de John Horton Conway y la era de Stephen Wolfram.
La primera etapa la inicia von Neumann, quien una vez terminada su participación en el desarrollo y terminación de la primera computadora ENIAC tenía en mente desarrollar una máquina con la capacidad de construir a partir de sí misma otras máquinas (auto-reproducción) y soportar comportamiento complejo. Con la ayuda de su amigo Stanislaw Ulam, von Neumann implementa la teoría de los autómatas celulares en un vector de dos dimensiones (donde representa el conjunto de los enteros). El vector es llamado el espacio de evoluciones y cada una de las posiciones (llamadas células) en el vector toma un valor del conjunto de estados . La función de transición que determina el comportamiento del autómata celular utiliza la vecindad de von Neumann, que consiste en un elemento central (llamada célula central) y sus vecinos que son las células , , y (es decir, la célula en cuestión y sus células vecinas más próximas, arriba, abajo, izquierda y derecha, respectivamente).
En 1970, John Horton Conway dio a conocer el autómata celular que probablemente sea el más conocido: el Juego de la vida (Life), publicado por Martin Gardner en su columna Mathematical Games en la revista Scientific American. Life ocupa una cuadrícula (lattice bidimensional) donde se coloca al inicio un patrón de células "vivas" o "muertas". La vecindad para cada célula son ocho: los vecinos formados por la vecindad de Von Neumann y las cuatro células de las dos diagonales (esta vecindad se conoce como vecindad de Moore). De manera repetida, se aplican simultáneamente sobre todas las células de la cuadrícula las siguientes 3 reglas:
Una de las características más importantes de Life es su capacidad de realizar cómputo universal, es decir, que con una distribución inicial apropiada de células vivas y muertas, Life se puede convertir en una computadora de propósito general (máquina de Turing).
Stephen Wolframha realizado numerosas investigaciones sobre el comportamiento cualitativo de los A.C. Con base en su trabajo sobre AC unidimensionales, con dos o tres estados, sobre configuraciones periódicas que se presentan en el A.C., observó sus evoluciones para configuraciones iniciales aleatorias. Así, dada una regla, el A.C. exhibe diferentes comportamientos para diferentes condiciones iniciales.
De esta manera, Wolfram clasificó el comportamiento cualitativo de los A.C. unidimensionales. De acuerdo con esto, un AC pertenece a una de las siguientes clases:
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í. De hecho, cualquier sistema real al que se le puedan analogar los conceptos de "vecindad", "estados de los componentes" y "función de transición" es candidato para ser modelado por un A.C.
Las características de los autómatas celulares harán que dichos modelos sean discretos en tiempo, espacio o ambos, dependiendo de la variante de la definición de A.C. que se use. Algunos ejemplos de áreas en donde se utilizan los autómatas celulares son:
El AC no trivial más simple consiste en una retícula unidimensional de células que sólo pueden tener dos estados (« 0 » o « 1 »), con un vecindario constituido, para cada célula, por ella misma y por las dos células adyacentes (23=8 configuraciones posibles). Existen 28=256 modos de definir cuál ha de ser el estado de una célula en la generación siguiente para cada una de estas configuraciones, luego existen 256 AC diferentes de este tipo.
Consideremos el AC definido por la tabla siguiente, que nos da la regla de evolución: