Formica di Langton: differenze tra le versioni
entro fine 2008 finisco di tradurre |
(Nessuna differenza)
|
Versione delle 18:07, 17 dic 2008
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. È stata inventata nel 1986 da Chris 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 "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.