Langton’s Ant

E’ un automa a stati finiti bidimensionale con un insieme di regole molto semplice ma in grado di creare figure molto complicate

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

  • su una cella ROSSA, gira a destra di 90° e scambia il colore della cella con il BLU
  • su una cella BLU, gira a sinistra di 90° e scambia il colore della cella con il ROSSO

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.