Formiga de Langton

En computació, la formiga de Langton és una màquina de Turing bidimensional amb un conjunt de normes molt simple, que tot i això dona lloc a comportaments emergents complexes. La formiga de Langton clàssica opera sobre una graella espacial quadrada, en la que cada cel·la pot tenir un de dos estats (blanca o negra). Va ser inventada per Chris Langton l'any 1986 i la seva universalitat va ser demostrada l'any 2000. La idea ha estat generalitzada de diverses maneres, entre elles turmites que agreguen més estats, normes per afegir més colors, graelles tridimensionals o finites, entre d'altres.

Formiga de Langton després de 11000 iteracions. El píxel vermell indica la posició actual de la formiga.

Versió clàssica

Animació dels primers 200 passos de la formiga de Langton clàssica.

Cada quadrat de l'entramat es pinta de blanc o negre. S'identifica arbitràriament un quadrat com la «formiga». La formiga sempre està mirant en una de les quatre direccions cardinals i es mou un quadrat cada vegada, d'acord amb les següents normes:

• Si està sobre un quadrat blanc, canvia el color del quadrat, gira 90 graus a l'esquerra i avança un quadrat.
• Si està sobre un quadrat negre, canvia el color del quadrat, gira 90 graus a la dreta i avança un quadrat.

La formiga de Langton també es pot descriure com un autòmat cel·lular, on la graella es pinta de blanc o negre i la formiga es pinta d'un de vuit colors diferents, depenent del color del quadrat al que es troba i de la direcció a la que està mirant.

Comportament

Tot i la simplicitat de les normes de moviment, els comportaments de la formiga són tan complexos que han estat objecte de múltiples investigacions.

Començant per una graella totalment blanca, la versió clàssica presenta tres tipus de comportament aparents:

• Simplicitat: Durant els primers centenars de passos, la formiga crea patrons senzills i freqüentment simètrics.
• Caos: Després d'aquesta primera fase apareix un patró gran i irregular. La formiga segueix un camí aparentment atzarós fins a aproximadament 10.000 passos.
• Ordre emergent: Finalment la formiga comença a construir una "xemeneia", un patró atractor de 104 passos que es va repetint indefinidament.

La conjectura de Cohen-Kong estipula que independentment del patró original a la graella, sempre s'acaba arribant a la distribució necessària perquè la formiga construeixi la "xemeneia". Aquesta hipòtesi encara no ha estat demostrada ni refutada; l'únic que es coneix és que la trajectòria de la formiga no té un límit, independentment de l'estat inicial. Aquesta demostració es coneix com el Teorema de Bunimovitch-Troubetzkoy.

Teorema de Bunimovitch-Troubetzkoy

Classificació de les cel·les de la graella segons la direcció d'entrada.

Els moviments de la formiga s'alternen entre verticals i horitzontals. Això permet classificar les cel·les de la graella en dos conjunts: cel·les a les que s'entra horitzontalment i es surt verticalment (cel·les H) i cel·les a les que s'entra verticalment i es surt horitzontalment (cel·les V).

Suposant que existís una formiga amb trajectòria acotada, aquesta formiga només podria visitar un nombre finit d'estats (fins a 4 direccions i 2 colors per cada cel·la en la trajectòria). Per tant, atès que la formiga es mou infinitament, en algun moment ha de repetir un estat i a partir d'aquest moment quedarà atrapada infinitament en un cicle. A més, com que aquest cicle és de longitud finita, ha de ser acotat i per tant té "cantonades"; en particular ha de tenir cantonades inferiors-esquerres, és a dir, cel·les les quals les seves veïnes inferior i esquerra no formen part del cicle.

A l'agafar una d'aquestes cantonades és possible veure que la segona vegada que el cicle passa per ella (hi passa infinits cops) el seu color és blanc si és una cel·la H (només hi pot haver entrat per la dreta per sortir per la part superior) o negre si és una cel·la V (només hi pot haver entrat per la part superior per sortir per la dreta). Al passar per la cel·la el seu color canvia, per tant la pròxima vegada que hi passi el color serà el contrari d'abans; negre si és H i blanc si és V, lo qual és una contradicció perquè llavors la formiga aniria a una cel·la que queda fora del cicle. Aquesta contradicció permet concloure que aquest cicle no pot existir, i per tant la formiga no pot tenir una trajectòria acotada.

Universalitat

L'ant 2000, Gajardo et al. van mostrar una construcció que calcula qualsevol circuit binari utilitzant la trajectòria d'una única formiga de Langton. En termes de la teoria de la computació, i referint-se concretament en la complexitat de la computació, això vol dir que el problema de saber si la trajectòria d'una formiga de Langton clàssica passa per una determinada cel·la, és P-hard (redueix un problema P-complet, el càlcul d'un circuit binari). Per tant, seria possible simular una màquina de Turing utilitzant la trajectòria de la formiga. Això significa que la formiga, tot i tenir unes normes tan bàsiques, és capaç de realitzar computació universal, cosa que implica que hi ha problemes indecidibles sobre el comportant de la formiga de Langton clàssica.

Versió de Turk-Propp

Greg Turk i Jim Propp van proposar que les normes de la versió clàssica fossin generalitzades per permetre que les cel·les tinguessin més de dos colors, on cada color està associat a un sentit de gir; R per dreta (right) i L per esquerra (left). Per exemple, la formiga "RRLL" es mou en una graella bidimensional amb cel·les que s'alternen entre quatre colors, els dos primers indiquen un gir a la dreta i els altres a l'esquerra. La versió clàssica per tant tindria la nomenclatura "RL".

La introducció de nous colors dona lloc a comportaments diferents als observats a la versió clàssica, per exemple la formiga "RRLL" genera sempre patrons simètrics, mentre que la "RLR" creix de forma caòtica (de fet, es desconeix si en algun moment arriba a crear una xemeneia).

• Exemples de patrons produïts per formigues de més de 2 colors:
• 
  RLR: Creix caòticament. Es desconeix si en algun moment construeix una xemeneia.
• 
  LLRR: Creix simètricament.
• 
  LRRRRRLLR: Forma patrons quadrats al seu voltant i els emplena.
• 
  LLRRRLRLRLLR: Crea una xemeneia intricada.
• 
  RRLLLRLLLRRR: Patrons triangulars cada cop més grans.

Tot i haver-hi aquests comportaments tan variats, el teorema de Bunimovitch-Troubetzkoy segueix sent vàlid per qualsevol formiga que tingui almenys una R i una L a la seva cadena característica. Això implica que el recorregut d'una formiga no està limitat a un espai finit i cap formiga genera camins cíclics repetitius.

A més de generalitzar les normes per múltiples colors, Turk i Propp van introduir una nomenclatura que assigna un enter a cada una d'aquestes formigues. Per fer-ho s'obvien les simetries, ja que per exemple "LRL" i "RLR" es comporten de manera isomorfa. L'obtenció d'aquest índex es fa de la següent manera: s'agafa l'equivalent de la cadena que comenci per L, i es converteixen les L en 1 i les D en 0. Això obté un nombre binari que és convertit en nombre decimal.

Propp també va observar que la trajectòria creixierà simètricament quan la cadena, vista de manera cíclica, tingui només blocs parells tant de R com de D.

Altres versions

Basant-se en l'extensió en diversos colors, Leonid Bunimovich planteja la possibilitat d'utilitzar una graella tridimensional. La idea consisteix en afegir dos possibles sentits de gir i indicar-ho a la cadena: U per un gir de 90° cap a dalt U (up) i D cap avall (down). D'aquesta manera, cada color està associat a un dels quatre possibles sentits i la formiga es pot moure fora del seu pla inicial. Les cadenes característiques de formigues de Langton en 3 dimensions han de tenir almenys 3 lletres de longitud, perquè si en tenen 2 se'n pot obtenir un símil bidireccional. Aquestes formigues comparteixen diverses característiques amb la versió bidimensional, especialment la tendència a crear xemeneies.

També s'ha intentat estudiar el comportament de la formiga en espais finits col·locant-la en un pla toroïdal (al sortir dels marges del pla apareix al costat contrari). Aquestes també formen xemeneies, però es veuen interrompudes quan la formiga torna a trobar el seu propi rastre. Hi ha moltes qüestions encara no resoltes en aquest tipus de formigues; per exemple no se sap si trepitgen totes les cel·les ni si ho fan amb la mateixa freqüència.