La formica di Langton | Autostrada, regole e turmiti

Le regole

La formica cammina su una griglia infinita di quadrati. Ogni casella è bianca o nera e la formica è rivolta a nord, est, sud o ovest. Il colore sotto le sue zampe decide l’intera mossa successiva. Su una casella bianca gira di 90° a destra (in senso orario), colora la casella di nero e avanza di una cella. Su una casella nera gira di 90° a sinistra (in senso antiorario), colora la casella di bianco e avanza di una cella. Non c’è casualità. Avvia due volte la stessa partenza e otterrai la stessa immagine.

Tre fasi

Avvia la formica su una griglia bianca vuota e il suo comportamento si divide in tre tratti ben noti. 1. Semplicità e simmetria, dal passo 1 a circa il passo 500. La scia è piccola e spesso simmetrica. 2. Caos, da circa il passo 500 a circa il passo 10.000. La formica resta intrappolata nel proprio percorso. L’immagine sembra rumore, anche se ogni passo è stabilito in anticipo. 3. L’autostrada, dopo circa 10.000 passi. La formica si blocca in un ciclo di 104 passi. Ogni ciclo aggiunge un blocco diagonale ripetuto e sposta la formica di due celle di lato e di due celle in avanti. Una volta iniziato su una griglia libera, il ciclo continua per sempre e la formica costruisce un’autostrada dritta a partire dal caos.

Perché è importante

La formica è una delle dimostrazioni più chiare di emergenza: strutture complicate e difficili da prevedere nate da una manciata di regole locali. È anche Turing-completa. Con uno schema iniziale adatto, lo stesso tipo di regola può eseguire qualsiasi calcolo possibile per un computer generico. Non serve questo apparato per godersi l’immagine. L’autostrada è già la sorpresa.

Colori, colonie, esagoni e turmiti

L’idea è stata estesa in diverse direzioni. Le regole multicolore sostituiscono il bianco e nero con un elenco di svolte, scritto come una stringa di L e R. RL è la formica classica. RLR, LLRR e LRRRRRLLR danno a ogni colore la propria svolta. La formica scrive il colore successivo dell’elenco e alcune di queste regole fanno crescere figure geometriche simmetriche invece di un’unica autostrada. Più formiche condividono una griglia. Quando le loro scie si incontrano possono spezzare un’autostrada o tessere un motivo che nessuna formica costruirebbe da sola. Una griglia esagonale dà alla formica sei direzioni. Una svolta a destra o a sinistra è allora di 60° invece di 90°. Una turmite conserva uno stato interno, una piccola memoria. La svolta e il colore scritto dipendono sia dalla cella sia da quello stato, quindi la regola stessa cambia mentre la formica cammina. Spirale, Trama e Deriva nell’app sono turmiti a due stati e due colori.

Esplorala in PictorX

Apri Formica di Langton per avviare la formica classica, saltare nella fase caotica o partire dall’autostrada. Digita una regola di svolta, aggiungi formiche, passa alla griglia esagonale o scegli una turmite. Trascina per spostarti, scorri per lo zoom, colora celle e aggiungi altre formiche. Salva un PNG o apri la tela nell’editor di PictorX. Abbinala alla Congettura di Collatz o al Laboratorio di reazione-diffusione per altre regole semplici con immagini sorprendenti.

Domande frequenti

Chi ha inventato la formica di Langton?

Chris Langton, nel 1986. È una macchina di Turing bidimensionale: una formica, una griglia infinita e una svolta che dipende solo dal colore della cella corrente.

Ogni schema iniziale costruisce un’autostrada?

La griglia vuota sì, dopo circa 10.000 passi, e il ciclo di 104 passi continua una volta che la formica è sull’autostrada. Altri schemi iniziali e altre regole possono costruire autostrade, restare limitati o crescere con un’altra forma. Il preferito «Autostrada» dell’app colloca la formica classica subito dopo l’inizio del ciclo.

Che cosa significa la stringa della regola?

Ogni carattere è la svolta per un colore. R significa girare a destra, L girare a sinistra. Dopo la svolta, la formica porta la cella al colore successivo e avanza. RL è bianco e nero. Una stringa più lunga è una formica multicolore.

In che cosa una turmite è diversa dalla formica?

La formica classica non ha memoria oltre alla griglia. Una turmite ha anche uno stato interno. Il colore della cella e quello stato scelgono insieme il colore da scrivere, la svolta e lo stato successivo.