Formica di Langton

La formica di Langton è un automa a stati finiti bidimensionale con un insieme di regole molto semplice ma in grado di creare figure molto complicate. È stato inventato nel 1986 da Chris Langton.

Formica di Langton

Regole

Le celle di una griglia sono colorate ognuna di bianco o nero. La "formica" sta su uno di essi.

La formica può spostarsi in ognuna delle 4 direzioni cardinali, seguendo le seguenti regole:

• su una cella nera, gira a destra di 90°, scambia il colore della cella, si sposta avanti di una cella
• su una cella bianca, gira a sinistra di 90°, scambia il colore della cella, si sposta avanti di una cella

Queste due semplici regole portano ad un comportamento sorprendentemente complesso: se avviate su una griglia completamente bianca, dopo un periodo di apparente caos la formica comincia a costruire un motivo ricorrente di 104 passi che si ripete all'infinito. Altre configurazioni iniziali sembrano convergere a simili schemi ripetitivi, suggerendo che questa cosiddetta "autostrada" sia un attrattore della formica di Langton; tuttavia, nessuno è riuscito a dimostrare che ciò valga per ogni configurazione iniziale.

È stato invece dimostrato che la formica di Langton è Turing-equivalente.

Questo automa può anche essere visto come un automa cellulare, in cui ai colori bianco e nero che riempiono la griglia vengono aggiunti altri 8 colori per la cella dove si trova la formica; essi codificano il colore di quella cella e la direzione della formica (e sono gli unici che danno origine a comportamenti dinamici).

Possibili versioni estese

Tre formiche di Langton con colori diversi si muovono in uno spazio toroidale .

Un'estensione semplice del concetto di formica di Langton è quella in cui vengono utilizzati più di due colori, che la formica cambia in modo ciclico. Per indicare schematicamente estensioni di questo tipo, è sufficiente specificare, per ognuno dei colori, una lettera che indichi quale direzione la formica prenda in corrispondenza: D o S. Secondo questo schema, la formica di Langton "classica" segue la regola SD.

Alcune di queste formiche di Langton "estese" producono configurazioni che si ripetono sempre simmetricamente. Uno dei più semplici esempi è dato dalla formica DSSD. Una condizione sufficiente perché ciò accada è che la regola della formica, sia composta da coppie consecutive di lettere uguali (eventualmente dopo avere spostato l'ultima lettera all'inizio).

Universalità della formica di Langton

Nel 2000, Gajardo ed altri sono riusciti a descrivere una configurazione che calcola il valore di un qualsiasi circuito booleano sfruttando la traiettoria di una singola formica di Langton.^[1] Ciò implica che è possibile simulare una macchina di Turing utilizzando la traiettoria della formica come computazione, ovvero che la formica di Langton, vista come meccanismo di calcolo formale, è turing-equivalente.