La Cibernética y la investigación en Teoría de Sistemas siguieron prácticamente el mismo camino desde la publicación de "Cybernetics" por N. Wiener en 1948, hasta el punto de confundirse, a pesar de esto algunos autores insisten en las diferencias. Esta confluencia crea el problema de cómo puede caracterizarse computacionalmente "lo vivo". Uno de los hombres más relevantes de la Informática, von Neumann, a quien debemos la arquitectura de los ordenadores programables actuales, realizó importantes avances en la Informática Teórica que hasta hace pocos años fueron relegados en la historia oficial a un plano meramente anecdótico. A través del modelo computacional de los Autómatas Celulares, desarrollado ya en los últimos años 40, intentó caracterizar una característica primordial de los sistemas vivientes: la autorreproducción. El razonamiento de von Neumann, análogo al Test de Turing en la Inteligencia Artificial, se resume así según Langton:
-La autorreproducción, se lleva a cabo por una máquina bioquímica altamente compleja.
-Entonces, el comportamiento de esa máquina es descriptible como una secuencia lógica de etapas.
-Luego, si el algoritmo se puede llevar a cabo por alguna máquina, existe una máquina de Turing que hace lo mismo (tesis de Church).
-Por lo tanto, se requiere modelar una máquina de Turing capaz de autorreproducirse. Si esta máquina de Turing autorreproductiva existe, es plausible que los procesos de autorreproducción biológicos sean algorítmicamente descriptibles, y por lo tanto la vida puede simularse en máquinas.
Von Neumann consiguió bosquejar una máquina de Turing autorreproductiva utilizando los Autómatas Celulares. Recordemos que Turing especificó una máquina universal capaz de recoger en la cinta la codificación de cualquier otra máquina (a través de un número natural) y los datos para ésta (también naturales), y ejecutar dicha máquina sobre esos datos. También demostró el resultado análogo al de el teorema de incompletitud de Godel, conocido como el Problema de Parada: el problema de decidir si una máquina codificada por un número natural n convergerá devolviendo un resultado al darle como dato el mismo natural n no es decidible.
El problema de von Neumman no era por lo tanto trivial. Un organismo vivo desarrollado A tiene un código genético Ø(A). Denotemos por (A,Ø(A)) al organismo completo, que incluye su autodescripción. A estaría representado por una máquina de Turing, mientras que Ø(A) sería el código de dicha máquina. A partir de dicho código Ø(A), por reproducción asexual (si no media mutación) se desarrolla otro organismo A que también tiene el mismo código genético. Se trataría de encontrar (HEA92) una máquina de Turing copiadora universal U tal que a partir de (A,Ø(A)) produzca dos organismos (A,Ø(A)), (A,Ø(A)). En concreto, cuando le damos a U el organismo (U,Ø(U)), la máquina produciría una autorréplica. El problema, es que el código de esta máquina, Ø(A,Ø(A))=Ø(X), debería producir al aplicarse U el resultado (X,Ø(X))=((A,Ø(A)),Ø(A,Ø(A)), y así infinitamente. Su idea era realizar un modelo material de dicha máquina autorreplicativa. Pero von Neumman prefirió para este fin una máquina U que no es una máquina de Turing, pero si un modelo de computo equivalente las máquinas de Turing: los autómatas celulares. Un autómata celular A=(T, N, M) está formado por red D-dimensional T, cuyos nodos están ocupados por autómatas finitos idénticos M, que mantienen entre sí relaciones de vecindad definidas por una plantilla de entorno N.
Cada célula está ocupada por autómatas finito M=(Z,A), todos idénticos. La célula puede tomar un estado dentro de un conjunto Z, caracterizado por un color. Se reserva un color especial, el estado quiescente qp, como color de fondo.
Lo más común es tomar la dimensión D=2, y T es una matriz m x n, aunque para propósitos teóricos como el de von Neumann se supone que la matriz es infinita en las cuatro direcciones. Se pueden tomar diversas plantillas de entorno N, pero las más comunes son el entorno de 5 elementos, en el que cada célula se conecta con sus cuatro vecinos situados en las direcciones N, E, S y O y donde el primer elemento del entorno corresponde a la dirección de la célula, C. N=(C,N,E, S, O) En el entorno de 9 elementos: N=(C, N, NE, E, SE, S, SO, O)
Cada autómata finito i realiza transiciones de un estado a otro tomando como entrada el propio estado y los estados de sus vecinos N (i) en un instante de tiempo t.
Todos los autómatas finitos realizan sus transiciones sincrónicamente a partir de una configuración de estados iniciales, esto es un movimiento del autómata celular. Un computo del autómata celular es una secuencia de movimientos. Si la función de transición de M es A, el cambio de estado de una célula a otra se realiza como en el siguiente ejemplo:
Sea N(i)=(qi1, qi2, qi3, qi4, qi5) el entorno de estados de la célula i. La expresión sigma(qi1, qi2, qi3, qi4, qi5)=q', quiere decir que toda célula que en el instante t tenga las posiciones definidas por el entorno N =(C, N, E, S, O) en los estados (qi1, qi2, qi3, qi4, qi5), pasará en el instante t+1 al estado q'. Las casillas de los bordes reciben tratamiento especial, bien cerrando la red come un toro o bien suponiendo que existe un marco formado por células en estado aquiescente. Se parte siempre de una configuración inicial, es decir de una asignación inicial de estados a las células, y el computo sigue hasta que se alcanza un punto fijo, pero puede ocurrir también que el computo sea infinito. Si la matriz es finita, siempre se alcanzará un ciclo de configuraciones que se repite infinitamente.
Los autómatas celulares se popularizaron con el llamado Juego de la Vida. Se trata de una matriz mxn en la que las células pueden estar en dos estados: vivo o muerto, representados por los colores negro y blanco (aquiescente) respectivamente. N es la plantilla de entorno de 9 elementos. Sea N(i) el entorno de estados de la célula i. La función de transición representa una constricción de tipo biológico: una célula sólo puede estar viva si en el entorno hay suficientes células vivas, al menos 3, para asegurar la reproducción y que la casilla siga ocupada, y no demasiadas células vivas, como mucho 4, para asegurar que no hay excesiva competencia y el organsimo pueda sobrevivir. Por negros (N(i)) denotemos el número de células vivas que hay en el entorno. Las dinámicas que interesa estudiar son las que permiten que una población sobreviva, es decir, que no se alcance la configuración de un tablero en estado muerto.
Aunque von Neumann apuntó a una demostración de que la Máquina de Turing puede simularse mediante autómatas celulares utilizando 29 estados por célula y entorno de 5 elementos, aunque no llegó a implementarse nunca.
