Hormiga de Langton
La hormiga de Langton es un 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 turmites 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 bien negro. Se identifica arbitrariamente un cuadrado como la «hormiga». La hormiga siempre está mirando en una de las cuatro direcciones cardinales y se mueve un cuadrado cada vez, de acuerdo con las siguientes reglas:
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 del cuadrado sobre el que esté y de la dirección en que esté mirando.
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,:
Todas las configuraciones finitas puestas a prueba, convergen eventualmente al mismo patrón repetitivo, sugiriendo que la «avenida» es una suerte de atractor de la hormiga de Langton, pero todavía nadie ha podido demostrar si eso es cierto para todas las configuraciones iniciales finitas, esta es la conjetura de Cohen-Kong. Solo se sabe que la trayectoria de la hormiga no tiene un límite, sin importar la configuración inicial, tal como lo demuestran Bunimovitch y Troubetzkoy.
Para demostrar el teorema de Bunimovitch-Troubetzkoy, es necesario primero hacer una observación:
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.
Greg Turk y Jim Propp propusieron que las reglas de la versión clásica fueran generalizadas para permitir que los cuadrados tomen más de dos colores, en donde cada color está asociado a un sentido de giro (90° a la derecha 'D' o 90° a la izquierda 'I'). Así, por ejemplo, la hormiga "DDII" se mueve en una rejilla bidimensional cuyas celdas se alternan entre 4 colores, los dos primeros indican un giro a la derecha y los dos siguientes un giro a la izquierda, mientras que la versión clásica sería bajo esta nomenclatura la hormiga "DI".
La introducción de nuevos colores da lugar a comportamientos distintos a los observados en la versión clásica, por ejemplo, algunas hormigas como la "DDII" genera siempre patrones simétricos, mientras que otras, como la hormiga "DID" crece de forma caótica (de hecho, se desconoce si en algún momento llega a generar una avenida).
DID: crece caóticamente. Se desconoce si en algún momento construye una avenida.
IIDD: crece simétricamente.
IDDDDDIID: forma patrones cuadrados a su alrededor y los rellena.
IIDDDIDIDIID: crea una avenida intrincada.
DDIIIDIIIDDD: crea patrones triangulares cada vez más grandes.
A pesar de comportamientos tan variados, el Teorema de Bunimovitch-Troubetzkoy sigue siendo válido para cualquier hormiga construida de esta manera (siempre y cuando tenga al menos una D y una I en su cadena característica). Esto quiere decir que el recorrido de una hormiga no está limitado a un espacio finito y, entre otras cosas, esto implica que ninguna hormiga genera caminos cíclicos repetitivos.
Además de extender las reglas para múltiples colores, Turk y Propp introdujeron una nomenclatura que a cada una de estas hormigas le asigna un entero. Esta nomenclatura obvía las simetrías, por ejemplo, teniendo en cuenta que las hormigas "IID" y "DDI" se comportan de manera isomorfa, a ambas se les asigna el mismo número y se estudian como si fueran la misma.
Para calcular el número de una hormiga, se toma la cadena equivalente que empiece por 'I' y luego se reemplazan las 'I' por 1 y las 'D' por 0. El resultado se convierte de binario a decimal y el resultado es un número que define sin ambigüedad la hormiga inicial.
Cuándo Propp realizó pruebas con hormigas generadas por cadenas de longitud 4 y menores, notó la aparición de patrones simétricos, situación que en la versión clásica apenas se da un par de veces durante los primeros 200 pasos y no vuelve a suceder. Las hormigas "IIDD" y "IDDI" (con números 12 y 9 respectivamente) eran las que se comportaban de esta peculiar manera. Después, al realizar pruebas con hormigas de longitudes 5 y 6, aparecieron otras hormigas con comportamientos simétricos ("IDDDDI", "IDDIII", "IIDDDD", "IIDDII", "IIIDDI" y "IIIIDD", con números 33, 39, 48, 51, 57 y 60) halló una regularidad conocida como la "Propiedad de las subcadenas de longitud par" ("Even run lenght property" en inglés), que consiste en que, vista cíclicamente, la cadena característica de todas estas hormigas está compuesta por parejas de letras iguales (es decir, la longitud de todas las subcadenas maximales de letras iguales es par). Posteriormente se demostró que estas observaciones no fueron casualidad, y que en efecto, cualquier hormiga generada a partir de una cadena que cumpla con esta propiedad generará patrones simétricos con centro en la posición inicial.
Una consecuencia, también visible en los ejemplos con hormigas de longitud menor o igual a 6, es el hecho de que el número correspondiente a todas estas hormigas es divisible por 3, esto se ve explicado en que y por lo tanto, el criterio de divisibilidad por 3, para números escritos en binario, es equivalente al criterio de divisibilidad por 11 para números en base 10 (ver Criterios de divisibilidad y Aritmética modular).
Basándose en la extensión a varios colores, Leonid Bunimovich plantea además la posibilidad de poner a la hormiga de Langton en una rejilla tridimensional. La idea consiste en añadir dos posibles sentidos de giro (90° hacia arriba 'A' y 90° hacia abajo 'B'), así cada color está asociado a uno de los cuatro posibles sentidos ('I', 'D', 'A' o 'B') y la hormiga se puede mover por fuera de su plano inicial. Las cadenas características de hormigas de Langton en 3 dimensiones deben tener al menos 3 letras de longitud, pues de tener 2 podría ser una hormiga bidimensional ("ID" y "AB") o cíclica ("IA", "IB", "DA" y "DB").
El estudio de estas hormigas exige más recursos de cómputo (tiempo y memoria), de manera que resultan difíciles de analizar. Aun así, la experimentación ha permitido observar que estas hormigas comparten varias características con la versión de dos dimensiones, en especial la tendencia de muchas de ellas a generar avenidas.
También se ha intentado estudiar el comportamiento de la hormiga de Langton en espacios finitos, haciendo que cuando la hormiga sale por un costado de la rejilla aparezca en la celda correspondiente del lado opuesto. Esta construcción es equivalente a colocar una hormiga de Langton sobre una rejilla en la superficie de un toro. Las hormigas en espacios finitos también tienden a generar avenidas, sin embargo estas se ven interrumpidas cuándo la hormiga se encuentra con su propio rastro. Aun así, tras la colisión eventualmente vuelve a generar una nueva carretera.
En el estudio de hormigas de Langton en espacios finitos hay varias preguntas sin resolver, entre estas:
En el año 2000, Gajardo et al. mostraron una construcción que calcula cualquier circuito binario usando la trayectoria de una única hormiga de Langton. En términos de la teoría de la computación, esto quiere decir que el problema de saber si la trayectoria de una hormiga de Langton clásica pasa alguna vez por una celda dada, es P-Hard (pues reduce un problema P-completo, el cálculo de un circuito binario). Por lo tanto, sería posible simular una máquina de Turing usando la trayectoria de la hormiga. Esto significa que la hormiga es capaz de computación universal, lo cual también implica que hay problemas indecidibles acerca del comportamiento de la hormiga de Langton clásica.