autómata celular
Un autómata celular (pl. autómatas celulares , abreviatura CA ) es un modelo discreto de computación estudiado en la teoría de autómatas . Los autómatas celulares también se denominan espacios celulares , autómatas de teselado , estructuras homogéneas , estructuras celulares, estructuras de teselado y matrices iterativas . [2] Los autómatas celulares han encontrado aplicación en varias áreas, incluida la física , la biología teórica y el modelado de microestructuras .
Un autómata celular consta de una cuadrícula regular de celdas , cada una en uno de un número finito de estados , como encendido y apagado (en contraste con una red de mapa acoplada ). La cuadrícula puede tener cualquier número finito de dimensiones. Para cada celda, se define un conjunto de celdas denominado su vecindad en relación con la celda especificada. Se selecciona un estado inicial (tiempo t = 0) asignando un estado para cada celda. Se crea una nueva generación (avanzando t en 1), de acuerdo con alguna regla fija (generalmente, una función matemática) [3]que determina el nuevo estado de cada celda en términos del estado actual de la celda y los estados de las celdas en su vecindad. Normalmente, la regla para actualizar el estado de las celdas es la misma para cada celda y no cambia con el tiempo, y se aplica a toda la red simultáneamente, [4] aunque se conocen excepciones, como el autómata celular estocástico y el autómata celular asíncrono. .
El concepto fue descubierto originalmente en la década de 1940 por Stanislaw Ulam y John von Neumann cuando eran contemporáneos en el Laboratorio Nacional de Los Álamos . Si bien algunos lo estudiaron durante las décadas de 1950 y 1960, no fue hasta la década de 1970 y el Juego de la vida de Conway , un autómata celular bidimensional, que el interés en el tema se expandió más allá de la academia. En la década de 1980, Stephen Wolfram se comprometió en un estudio sistemático de autómatas celulares unidimensionales, o lo que él llama autómatas celulares elementales ; su asistente de investigación Matthew Cook demostró que una de estas reglas es Turing-completo .
Las clasificaciones principales de los autómatas celulares, tal como las describe Wolfram, están numeradas del uno al cuatro. Son, en orden, autómatas en los que los patrones generalmente se estabilizan en la homogeneidad , autómatas en los que los patrones evolucionan hacia estructuras en su mayoría estables u oscilantes, autómatas en los que los patrones evolucionan de una manera aparentemente caótica y autómatas en los que los patrones se vuelven extremadamente complejos y pueden durar varios años. mucho tiempo, con estructuras locales estables. Se piensa que esta última clase es computacionalmente universal , o capaz de simular una máquina de Turing . Los tipos especiales de autómatas celulares son reversibles , donde solo una única configuración conduce directamente a una posterior, y totalistas ., en el que el valor futuro de las celdas individuales solo depende del valor total de un grupo de celdas vecinas. Los autómatas celulares pueden simular una variedad de sistemas del mundo real, incluidos los biológicos y químicos.
