Origen

El origen de los autómatas celulares, dado a principios de los 50's, se identifica con el trabajo de John von Neumann sobre sistemas autorreproductivos [von Neumann 66]. Von Neumann interesado con las ideas de Turing acerca de un autómata universal, propone un autómata celular equivalente a una máquina universal de Turing [Codd 68]. Además, también quería averiguar que tan complejo podría ser construir un aparato autorreproductivo y como resolver el problema de alta confiabilidad relacionado con la complejidad de este dispositivo. En este mismo orden de ideas, él planteaba la necesidad de un mecanismo auto-reparador que utilizara partes que pudieran tener un mal funcionamiento.

En 1944, von Neumann se integra al proyecto ENIAC (Electronic Numerical Integrator and Computer) formando un grupo de trabajo cuyos intereses eran investigar problemas de computadoras, comunicaciones, control y series de tiempo; y para el sistema nervioso aspectos de comunicación y control [Preston 84]. En 1947, von Neumann empieza a estudiar la complejidad requerida para un dispositivo autorreproductor, empezando con modelos contínuos basados en ecuaciones diferenciales parciales no lineales y también usando la idea de un autómata cinético basado en los principios de Turing.

Debido a lo difícil de poder probar rigurosamente esta idea y escuchando la sugerencia de Stanislaw Ulam de utilizar un arreglo de elementos computables, von Neumann empieza a trabajar en un esquema basado en un espacio celular ocupando una malla de dos dimensiones, en el cual una célula podía tomar un valor de entre veintinueve posibles. Para su comportamiento cada célula depende del estado de ella misma y de sus cuatro células ``vecinas'' ortogonales: arriba, abajo, izquierda y derecha.

Figura 1.1: Vecindad de von Neumann

John von Neumann muere en 1957 antes de poder publicar su trabajo; pero este es publicado en 1966 mediante una edición por Arthur W. Burks [von Neumann 66]. Durante la decada de los 60's se trabajó fuertemente con la idea de autorreproducción destacando el trabajo de E. F. Codd [Codd 68] que realiza una variante del autómata de von Neumann pero con solo ocho estados posibles para cada célula. Otro trabajo importante se debe a Edward F. Moore y su concepto de ``Jardín del Edén'' [Moore 62]; el cual se tratará con mayor detalle en las secciones subsecuentes.