Automatas Discretas

2.- Autómatas
Un Autómata Celular (A.C.) es un modelo matemático 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
Un autómata celular, es un sistema dinámico discreto que evoluciona
en iteraciones a través de una regladeterminística, tal como un sistema
dinámico; las variables del sistema cambian como una función de sus valores
actuales. Pueden ser vistos como un proceso de cómputo en paralelo, donde
los datos son la configuración inicial.
2.1. Origen
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 deinflexión en el desarrollo de la teoría: la era de Von Neumann, la era de Martin Gardner y la era de Stephen Wolfram.
Trabajo de von Neumann.
El concepto de autómata celular (AC) fué desarrollado en los finales de los años 40's por John von Neumann; en esta época la manufactura de automóviles y bienes eléctricos empezaba a automatizarse y von Neumann se interesaba en crear una máquina que pudieramanufacturarse a sí misma, es decir, autorreproducirse.
Como carecía de los medios físicos y dispositivos técnicos que le permitieran hacer su proyecto, trató de hacerlo utilizando una forma muy simple y abstracta siguiendo una sugerencia de su amigo Stanislaw M. Ulam; esencialmente, Ulam sugirió un espacio cuadriculado donde cada cuadro podía ser ocupado por una célula dada que podía tener unnúmero finito de estados, el tiempo en este espacio avanzaba en lapsos discretos, cada célula hacía una transición a un nuevo estado dependiendo de su valor actual y el de las células en cada borde o vecinos.
 
Figura: Vecindad de von Neumann.
De este modo, von Neumann pudo desarrollar un AC que podía autorreproducirse, contaba con 29 estados diferentes para cada célula; cabe señalar quecuando en 1953 Watson y Crick descubrieron la estructura molecular del ADN observaron que tenía muchas de las características del modelo de von Neumann.
John von Neumann muere en 1957 y no publica su trabajo pero éste es editado por Burks en 1966, en ese mismo tiempo Codd trabaja en una variante del autómata de von Neumann con solo 8 estados.
Trabajo de John Conway.
En 1970, John Horton Conwaydio 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 los ocho vecinos formados por la vecindad de VonNeumann y las cuatro células de las dos diagonales (esta vecindad se conoce como vecindad de Moore).

Figura: Vecindad de Moore.
De manera repetida, se aplican simultáneamente sobre todas las células de la cuadrícula las siguientes 3 reglas:
1. Nacimiento: se reemplaza una célula muerta por una viva si dicha célula tiene exactamente 3 vecinos vivos.
2. Muerte: se reemplaza una célulaviva por una muerta si dicha célula no tiene más de 1 vecino vivo (muerte por aislamiento) o si tiene más de 3 vecinos vivos (muerte por sobrepoblación).
3. Supervivencia: una célula viva permanecerá en ese estado si tiene 2 o 3 vecinos vivos.
Con estas simples reglas, el juego de Life puede desarrollar un comportamiento bastante complejo muy parecido al de un grupo de microbios en una gota deagua que se observan bajo un microscopio, es por eso que ganó gran popularidad y produjo que muchos investigadores se dedicaran al estudio de los AC.
Trabajo de Stephen Wolfram.
Stephen Wolfram[] ha 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...