El juego de ``life'' es un autómata celular definido en un espacio bidimensional infinito, dividido en células biestables, que son actualizadas todas a un mismo tiempo progresivo en pasos discretos. Una célula está muerta o vacía si tiene estado 0, o bien, la célula está viva si su estado es 1. Cada célula esta relacionada con sus 8 células vecinas que distan de la célula central en una unidad. La regla de evolución que es aplicada a cada célula es la siguiente:
En un documento que se puede obtener en internet [51], y en el libro [1] se pueden revisar los detalles de cómo se ha construido una máquina universal de Turing con los patrones del juego de ``life'', en los siguientes párrafos se hará una descripción general del procedimiento utilizado para crear esta máquina universal.
Hay tres patrones de life que son básicos para la construcción de la máquina de Turing: un sumador, una celda de memoria y un bloque de memoria.
El primer patrón, el sumador, implementa la suma binaria de dos cadenas de gliders emitiendo una nueva cadena de gliders como resultado final de la suma. La figura 1.8 muestra un esquema de la construcción de un sumador binario en life. En este esquema, los datos (números) son codificados en secuencias binarias, en donde un glider representa un ``1'' y la ausencia de un glider representa un ``0'', dos 1's son representados por secuencias separadas por un espacio de 60 generaciones.
El sumador binario trabaja en dos etapas, la primera recibe los números en dos entradas. El resultado de la suma pasa como entrada a la segunda etapa, incluyendo su exceso (acarreo). Este exceso se agrega en la segunda etapa al resultado final, pudiendo generar de nuevo otro acarreo, que es devuelto a la segunda etapa para agregarse al siguiente bit y así sucesivamente.
El segundo patrón, una celda de memoria, tiene el objetivo de almacenar su contenido en una matriz junto con otras celdas de memoria. El contenido de la celda de memoria (que es un 1 o un 0) es el resultado de un choque de gliders que interactúan en otro patrón llamado pentadecathlon que produce un glider generando un ciclo debido al choque del glider con otro patrón que refleja el glider a 90 grados, que finalmente entra de nuevo y permanece en el ciclo indefinidamente.
El tercer patrón, el bloque de memoria [23,51], es una implementación de Dean Hickerson [23] basado en el trabajo de Marvin Minsky [37], quien empleó el concepto de un registro contador que tiene la capacidad de almacenar un número positivo. Las únicas operaciones que se requieren implementar son sumas, restas y verificaciones de valor 0. En la figura 1.9 se muestra esquemáticamente el diseño del bloque de memoria. Este diseño genera 4 gliders cada 120 generaciones que se bloquean por dos patrones bloqueadores que, si uno de ellos falta, se borra uno de los 4 gliders y los tres restantes hacen las operaciones de incremento. Si faltara el otro patrón bloqueador, entonces se borra un glider más, y los 2 restantes hacen la operación decremento.
La construcción de la máquina universal de Turing, utiliza los patrones descritos anteriormente y otros más que se describen con detalle y con ejemplos de sus evoluciones en [51]. Las celdas de memoria se ordenan en arreglos. El sumador proporciona la capacidad de incrementar un número binario que indica la dirección de la siguiente instrucción a ser leída, y la obtiene de la unidad de memoria, y el bloque de memoria es un registro contador que es capaz de almacenar un valor de cualquier tamaño.
La máquina de estados contiene la unidad de memoria que ha sido construida en base a celdas de memoria que mantienen los estados activados (1's) como cadenas de gliders moviendose en ciclos (ver figura 1.10), las direcciones de las localidades de memoria son obtenidas de las pilas, que simulan la cinta de la máquina de Turing. La actividad conjunta de las pilas simulan los movimientos de la cabeza lectora, intercambiando los datos representados como flujos de gliders.
|
El control de la pila es activado por una ``señal presente'' representada por un flujo de gliders para usarse como salida de la máquina de estados para determinar cuando hacer un pop y cuando hacer un push y también el símbolo que será agregado a la pila. El dato que resulta de la operación pop se envía a la máquina de estados para formar parte del siguiente ciclo en el arreglo de la memoria.
La máquina de estados es un arreglo de celdas de memoria, tiene dos entradas, una que representa el siguiente estado y luego se usa para seleccionar un renglón de ese arreglo y la otra entrada la usa una de las pilas que manda un flujo de gliders que representan el símbolo leído y luego se usa para seleccionar la columna del arreglo de celdas de memoria. Rendell concluye [51] que es muy fácil modificar el dato inicial en la pila para mostrar que la máquina de estados trabaja correctamente, solamente hay que poner una célula en un lugar adecuado, o modificar la secuencia de gliders que representan los datos. Para aplicaciones reales la máquina de Turing life se vuelve prácticamente inútil por el tiempo que requiere hacer las operaciones, pero ha servido para mostrar la extraordinaria capacidad del juego de ``life'' para construir máquinas de comportamiento complicado a partir de elementos simples.
