.

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.

VERSIÓN CLÁSICA

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.