LA
HORMIGA DE LANGTON
La hormiga
de Langton es una máquina de Turing bidimensional con un
conjunto de reglas muy sencillo, que sin embargo da lugar
a comportamientos emergentes complejos. La hormiga de Langton clásica opera sobre una rejilla
espacial cuadrada, en que cada celda puede estar en uno de
dos estados (blanca o negra, 1 o 0, viva o muerta, etc.). Fue inventada por Chris Langton en
1986 y su universalidad se demostró en el año 2000.la idea ha sido generalizada de varias
maneras, entre las que se encuentran turnitos que agregan más estados, así como reglas para
agregar nuevos colores, rejillas tridimensionales o finitas.
Cada cuadrado del entramado se colorea o bien blanco o negro
Si
está sobre un cuadrado negro, cambia el color del cuadrado, gira noventa grados
a la derecha y avanza un cuadrado.
La hormiga de Langton también se puede describir como un autómata celular, donde la rejilla se pinta de blanco o negro y la hormiga se pinta de uno de ocho colores diferentes, dependiendo del color cuadrado sobre el que esté y de la dirección en que esté mirando.
COMPORTAMIENTOS
Las
simples reglas que gobiernan a la hormiga de Langton llevan a comportamientos
complejos que han sido objeto de múltiples investigaciones. Comenzando con
una rejilla totalmente blanca, la versión clásica presenta tres tipos de
comportamiento aparentes:
Simplicidad:
durante los primeros cientos de pasos, la hormiga crea patrones sencillos y
frecuentemente simétricos.
Caos: después de varios cientos de pasos, aparece un patrón grande e irregular. La hormiga sigue un camino aparentemente azaroso hasta los 10.000 pasos.
DEMOSTRACIÓN
Clasificación
de las celdas de la grilla según su dirección de entrada .Los movimientos
de la Hormiga de Langton se alternan entre verticales y horizontales, esto
permite clasificar las celdas de la rejilla en dos conjuntos: uno es el de las
celdas a las que se entra horizontalmente y se sale verticalmente (llamadas
celdas H) y otro es el de las celdas a las que se entra verticalmente y se sale
horizontalmente (llamadas celdas V).Suponiendo que existiera una hormiga con
trayectoria acotada, esta hormiga solo podría visitar un número finito de
estados (hasta 4 direcciones y 2 colores por cada celda en la trayectoria). Por
lo tanto, debido a que la hormiga se mueve infinitamente, en algún momento ha
de repetir un estado y a partir de este momento quedará atrapada infinitamente
en un ciclo. Además, como dicho ciclo es de longitud finita, tiene que ser
acotado y por lo tanto tiene "esquinas", en particular debe tener
esquinas "inferiores-izquierdas" es decir, celdas cuyas vecinas
inferior e izquierda no forman parte del ciclo.
Al tomar una de estas esquinas, es posible ver que la segunda vez que el ciclo pasa por ella (el ciclo pasa por ella infinitas veces) su color es blanco si es una celda H (pues solo pudo haber entrado por su vecina derecha y girado 90° a favor de las manecillas del reloj para salir por su vecina superior) o negro si es una celda V (porque solo pudo haber entrado por su vecina superior y girado 90° en contra de las manecillas del reloj para salir por la derecha). Hay que tener en cuenta que al pasar por esta celda, su color cambia, y por lo tanto, la próxima vez que el ciclo pase por ella será negra si es una celda H y blanca si es una celda V, sin embargo esto es una contradicción, pues de ser una celda H tiene que llegar por su vecina derecha (pues la izquierda no forma parte del ciclo) y, si es de color negro, la hormiga gira a la izquierda y saldría por la vecina inferior (que no forma parte tampoco del ciclo), mientras que si se tratara de una celda V, tiene que llegar por la vecina superior (la inferior no está en el ciclo) y, al ser blanca, gira a la derecha y sale por la vecina izquierda (que tampoco lo está). En cualquiera de los dos casos, la hormiga tendría que llegar a una celda que no forma parte del ciclo, pero esto no es posible. Esta contradicción permite concluir que tal ciclo no existe y por lo tanto la trayectoria de la hormiga de Langton no puede estar acotada.
EL MODELO NAGEL SCRECKENBERG
El modelo
de Nagel y Schreckenberg (Na-Sch) es un modelo de flujo de tránsito
vehicular con un autómata celular (AC) probabilístico. Por ende,
es un modelo de espacio y tiempo discretos, donde
cada célula del autómata equivale ya sea a un vehículo en
movimiento con cierta velocidad o a un espacio vacío de la avenida
donde se encuentran los vehículos.
El
modelo Na-Sch original sirve para modelar autopistas de un carril (ya
sea abiertas o en circuito) con vehículos homogéneos.
Creado en 1992 por los científicos Kai Nagel y Michael Schreckenberg, el modelo Na-Sch se ha convertido en la base de muchos otros modelos discretos de tráfico vehicular, debido a su sencillez, que sin embargo, es capaz de modelar adecuadamente los fenómenos de congestionamiento en autopistas. Esto sucede ya que las gráficas de densidad de tráfico vs. flujo de tráfico son muy similares a las observadas empíricamente en diversas avenidas reales. Además, una simulación de este modelo permite observar las ondas de tráfico comunes en el flujo vehicular.
PARÁMETROS
Antes
de introducir las reglas del AC, se mencionan los parámetros relativos al
modelo:
Cada
vehículo tiene asociada una posición en la autopista. Al ser un AC
un espacio discreto, cada célula equivale a un vehículo o a una célula vacía.
Por convención, la posición es creciente a partir de un índice 0.
Cada
vehículo tiene una velocidad asociada, que es un valor máxima entero,
tal que: .
Es la velocidad
que puede alcanzar cualquiera de los vehículos.
Es
la probabilidad de que un vehículo reduzca su velocidad
aleatoriamente.Si , el modelo se conoce como Na-Sch Determinista, de
lo contrario se conoce como Na-Sch No Determinista. Esta probabilidad
puede verse como la causante de congestionamientos aleatorios en un flujo de
tráfico normal, causado en la realidad por alguna causa arbitraria (como una
distracción del conductor antes de comenzar a acelerar).
se
conoce como la brecha, que es la distancia en células que separa a un
vehículo de su predecesor (el vehículo inmediatamente adelante de él).
Debe
aclararse que la velocidad está dada en células por unidad de tiempo, y al
tratarse de un AC discreto, el tiempo corre en unidades, por lo que hablar de
una velocidad equivale a decir que un vehículo se
moverá células hacia adelante en un paso de tiempo.