Formica di Langton

La formica di Langton è la più semplice di una famiglia di formiche. Con n colori, numerati da 0 per il vuoto, una regola è una stringa $r = r_0 r_1 \cdots r_{n-1}$ di lettere R e L, una per colore. La formica di Langton usa RL. La formica si trova sulla casella p rivolta nella direzione d, e un passo è

La formica non ha memoria e vede solo il colore sotto di sé. Qui puoi osservarla creare ordine, poi un groviglio, poi una strada; puoi farla andare all’indietro, colorare caselle sul suo percorso e provare altre stringhe di lettere.

I colori sono gli stati della regola. Il piano non ha bordi e non collega un lato a quello opposto. La curva in cima al pannello conta le caselle colorate dopo ogni passo.

Partendo sul piano vuoto e rivolta verso l’alto, la formica crea prima piccoli disegni ordinati, alcuni simmetrici per una rotazione di mezzo giro, come al passo 473. Segue un groviglio dall’aspetto casuale per circa diecimila passi. Poi, dal passo 9 977, la formica ripete gli stessi 104 movimenti, traslando ogni ciclo di (−2, 2): due caselle a sinistra e due in basso. Sta costruendo una striscia diagonale chiamata autostrada, e ogni 104 passi aggiunge esattamente 12 caselle colorate. Si ripetono solo i movimenti della formica e la striscia sotto di lei. Il groviglio alle sue spalle resta dov’è.

Pochi cicli ripetuti non dimostrano nulla: il successivo potrebbe incontrare una casella colorata e deviare. Perciò la pagina garantisce una strada solo dopo un controllo. Al termine dell’ultimo ciclo, le caselle lette, traslate dello spostamento della formica, devono avere i colori che le caselle originali avevano prima del ciclo, e la formica deve essere rivolta nella stessa direzione di allora. Inoltre, in ogni ciclo futuro, le caselle oltre quelle del ciclo precedente devono essere vuote adesso e non devono essere state visitate da alcun ciclo a partire da quello controllato. Ogni ciclo incontra così esattamente ciò che ha incontrato il precedente e ripete gli stessi movimenti per sempre. La linea tratteggiata sulla curva segna l’inizio della ripetizione. Se davanti c’è una casella colorata, la pagina la cerchia e non dà garanzie.

Sul piano vuoto, dunque, la strada è dimostrata dal calcolo insieme a questo controllo. Per RL, tutte le griglie con un numero finito di caselle colorate finora provate finiscono per formare una strada, ma nessuno ha dimostrato che accada per tutte.

Ogni passo si può annullare. La formica guarda nella direzione in cui si è appena mossa: la casella da cui proviene è quindi dietro di lei, e il suo colore è avanzato di una posizione nel ciclo. Un passo indietro è

Quindi la griglia e la formica determinano lo stato di un passo prima. Indietro fa tornare la formica sui suoi passi secondo la regola, senza riprodurre una registrazione al contrario.

Con più lettere, ogni visita porta una casella al colore successivo. Dal piano vuoto, i pulsanti delle regole fanno crescere forme molto diverse: un disegno apparentemente simmetrico per LLRR, un quadrato quasi pieno per LRRRRRLLR, un triangolo in crescita per RRLLLRLLLRRR. Non si sa come finiscano questi tre casi. LLRRRLRLRLLR costruisce invece una strada dopo circa trentamila passi.

Chris Langton descrisse la formica nel 1986 come esempio di vita artificiale.