Qué son los Automátas Celulares
Patxi Echarte,
01. Sep, 2005,
7 Comentarios
Otros Informática
Revisando documentación en mi equipo y poniendo un poco de orden en toda ella he encontrado bastantes cosas en las que en su día trabajé y ahora tengo un poco olvidadas, aunque no por falta de interés en ellas, sino porque la vida, sobre todo la laboral, finalmente te lleva por otros derroteros. Una de estas cosas son los automátas celulares, a los cuales dediqué bastante tiempo durante la carrera.
Un autómata celular esta compuesto por una configuración y una tabla de transiciones. La configuración marca un estado de partida del mundo celular sobre el que se va a estudiar su evolución en el tiempo. Esta evolución viene definida por reglas para cada estado posible de la configuración, definidas mediante transiciones en la tabla de transiciones.
Los autómatas celulares fueron inventados en la década de los 50 por Von Neumann como resultado de su estudio sobre construcción de sistemas de complejidad no acotada. La solución que Von Neumann dio a este problema, fue que la construcción de dicho sistema fuese hecha por otro sistema computacional de menor complejidad, que a su vez habría sido construido por otro de menor complejidad, hasta llegar a uno cuya complejidad fuese abordable por el ser humano. Von Neumann observó que este tipo de problemas es algo común en la naturaleza, en la que se producen incrementos de complejidad como resultado de pequeñas variaciones en los procesos reproductivos de los seres vivos. Con esta base, acometió en la década de los 50 la definición de un dispositivo mecánico capaz de reproducirse, lo cual le llevó a la definición de los Autómatas Celulares como modelo de máquina abstracta formada por una red n-dimensional de autómatas finitos idénticos, conectados únicamente con sus vecinos inmediatos según unas relaciones de vecindad. Se puede hacer que cada autómata finito este conectado con sus cuatro vecinos situados en las direcciones N, S, E y O (malla con 4 vecinos) o podemos incluir conexiones con los autómatas situados en las esquinas (malla con ocho vecinos). Todas las células son idénticas y, por tanto, comparten el mismo conjunto de estados posibles Q. En el conjunto Q hay un estado especial llamado estado inicial q0, y a las células que están en dicho estado se las denomina células muertas. En un Autómata Celular, cada célula cambia de estado teniendo en cuenta su estado anterior y el de sus vecinas, de forma que todas las células del espacio celular cambian según la misma función de transición y que el cambio de estado es simultáneo en todo el espacio celular. Hay un problema con las células situadas en los bordes y esquinas del espacio celular, pues al no tener todos los vecinos, en principio no se les puede aplicar la función de transición. Para resolver esto, se puede hacer que el mundo esté acotado por células muertas (mundo no tórico), o se puede asumir que las células del borde superior son las vecinas inferiores de las del borde inferior, y que las del borde derecho están a la izquierda de las del borde izquierdo, etcétera.
La imagen que se muestra al comienzo de este texto es un ejemplo de automáta celular, conocido como autómata autorreproductor de Langton. Este autómata, partiendo de esa configuración inicial y con la tabla de transiciones que se muestra a continuación, basada en 8 estados posibles y cuatro vecinos, produce que el espacio celular se vaya ocupando por réplicas identicas a ella.
Tras algo más del 1000 pasos la configuración del mundo celular sería la siguiente. El mecanismo por el que estos autómatas se reproducen se basa en que cada automáta contiene un conjunto de estados que marcan su estructura, lo que en su equivalente biológico podríamos llamar su ADN. A partir de este código, el brazo reproductor que tiene cada autómata crea una copia del automáta original pasándole también ese ADN, de forma que el nuevo autómata creado pueda también comenzar a autorreproducirse.
Estas imágenes han sido obtenidas a partir de un procesador de automátas celulares de nombre PAC, que hicimos cuando estábamos en la carrera dentro del grupo de trabajo Autozel, del que formábamos parte Jesús Ibáñez Martínez-Conde, Oscar Barrera Herrera, Iker Aitor Azpeitia Lakuntza y yo mismo. La aplicación funciona sobre entornos Windows y está desarrollada en Delphi 2.0, tengo que revisarla un poco para ver qué siga funcionando correctamente, pero si es así espero publicarla en el web próximamente.
Más información
Muy interesante el comentario sobre los automatas, lo hace mas interesante cuando se publica resultados de trabajos realizados, no importa la magnitud del trabajo, sino, la aplicabilidad y la forma sencilla de explicarlo, lo que permite que cualquier persona lo entienda.
Gracias
Hola, estudio Ingenieria en Informatica, y estoy estudiando actualmete los Automatas Celulares, y necesito hacer el problema se Sistema Social, representado por las hormigas, si tienen informacion se los agradezco mandar a mi correo.
Gracias
Hola Miglid, no puedo ayudarte con lo del Sistema Social, lo único que puedo hacer es facilitarte si lo deseas el programa que construimos para ejecutar los autómatas, que quizás te venga bien.
Hola Patxi, estudio Ing en Sistemas en el Politecnico de Mexico, me llamo la atencion que dices tener un programa para ejecutar automatas, y yo intento hacer una simulacion de colision de automoviles por lo que me gustaria intentar el metodo de automatas para el modelado, no se si me harias favor de facilitarme ese programa. Gracias
Hola Lourdes. El programa es un simulador de autómatas celulares, de ningún otro tipo de autómatas, por lo que no sé si servirá para lo que estás buscando. Si te sirve dime y lo cuelgo para que lo tengas accesible.
Un saludo
Buen resumen de John Von Neuman, todos hablan de Conway pero el inventor no fue el.
Estoy estudiando Automatas celulares pero en 3 dimensiones X Y Z
aplicados a indices Bursatiles, atento a cualquier información o estudio al respecto de esta area gracias a todos, saludos.
vale picha