Gli automi cellulari | Gioco della vita, Regola 30, Regola 110 e altro

Le quattro parti fondamentali

Ogni automa cellulare è costruito con le stesse quattro parti. La griglia è lo spazio in cui vivono le celle. Può essere una linea unidimensionale, un piano bidimensionale come una scacchiera o perfino uno spazio tridimensionale. Gli stati sono ciò che una cella può essere. Nel caso più semplice una cella è binaria: nera o bianca, 1 o 0. Il vicinato è l’insieme delle celle che influenzano direttamente una cella. Su una griglia quadrata di solito è il vicinato di Moore, tutte le otto celle circostanti, oppure il vicinato di von Neumann, solo nord, est, sud e ovest. Le regole sono il cervello dell’automa: la logica che dà a ogni cella il suo nuovo stato. Per esempio: se sono viva ma ho meno di due vicine vive, muoio di solitudine. Ogni cella applica le stesse regole nello stesso istante.

1. Il Gioco della vita di Conway

Regole: B3/S23. Una cella viva sopravvive con 2 o 3 vicine vive. Una cella morta prende vita con esattamente 3. Ogni altra cella è morta nella generazione successiva. John Conway lo ideò nel 1970, e la rubrica di Martin Gardner su Scientific American lo rese famoso. Produce alianti, oscillatori e astronavi. Bill Gosper trovò il primo cannone di alianti lo stesso anno: uno schema che spara un nuovo aliante ogni 30 generazioni, per sempre. Il Gioco della vita può eseguire calcoli, poiché gli alianti possono trasportare segnali e scontrarsi come porte logiche. Soprattutto mostra un comportamento complesso che nasce da regole semplici.

Cannone di alianti di Gosper nel Gioco della vita che spara un flusso diagonale di alianti — Cannone di alianti di Gosper dopo 330 generazioni. Realizzato in PictorX.

2. Regola 30

Tipo: un automa cellulare elementare unidimensionale. Lo stato successivo di ogni cella dipende da sé stessa e dalle sue due vicine, e ogni generazione viene disegnata come una nuova riga sotto l’ultima. Stephen Wolfram introdusse la Regola 30 nel 1983. Partendo da una sola cella nera cresce un triangolo caotico. Sembra casuale nonostante la regola deterministica, così casuale che la sua colonna centrale è stata usata come generatore di numeri pseudocasuali. Lo stesso tipo di triangoli compare nel pigmento della conchiglia del Conus textile.

Triangolo della Regola 30 cresciuto da una sola cella nera, caotico a destra e a strisce a sinistra — Regola 30 da una cella nera, 224 generazioni. Realizzato in PictorX.

3. Regola 110

Tipo: un automa cellulare elementare unidimensionale, come la Regola 30, con una diversa tabella di otto risposte. È dimostrato che la Regola 110 è computazionalmente universale: Matthew Cook ha mostrato che con una prima riga adatta può emulare qualsiasi calcolo che un computer generico può eseguire. Ospita strutture mobili che viaggiano su uno sfondo ripetuto e interagiscono quando si incontrano. Quelle collisioni sono ciò che la dimostrazione usa come logica. Mostra come regole molto semplici possano emulare un calcolo arbitrario.

Regola 110 cresciuta da una cella a destra, che si espande verso sinistra in triangoli annidati — Regola 110 da una cella nera sul bordo destro. Realizzato in PictorX.

4. Brian's Brain

Stati: spento, acceso (attivo) e refrattario. Regole: una cella spenta si accende se esattamente 2 vicine sono accese. Una cella accesa diventa refrattaria. Una cella refrattaria si spegne. L’ha ideato Brian Silverman. Poiché una cella deve riposare per una generazione dopo essersi accesa, ogni impulso continua ad allontanarsi da dove è già passato. Il risultato è una folla di motivi semoventi che ricorda le onde nei mezzi eccitabili, come il tessuto nervoso o il muscolo cardiaco, e spesso sembra vivo e organico.

Brian's Brain che si espande da una macchia casuale, celle accese in giallo e scie che svaniscono in viola — Brian's Brain 70 generazioni dopo una macchia casuale, con scie che svaniscono. Realizzato in PictorX.

5. Wireworld

Stati: vuoto, testa di elettrone, coda di elettrone e conduttore. Regole: una testa diventa una coda, una coda diventa conduttore e un conduttore diventa una testa quando esattamente 1 o 2 delle sue vicine sono teste. Le celle vuote restano vuote. Anche Wireworld è stato ideato da Brian Silverman, nel 1987. Le celle conduttrici sono fili, e una testa seguita da una coda è un elettrone che vi scorre lungo. Può simulare circuiti elettronici: un anello di filo con un elettrone è un clock, una piccola tacca è un diodo e poche celle formano una porta logica. Al suo interno sono stati costruiti computer completi, come il computer Wireworld di David Moore e Mark Owen, che calcola numeri primi.

Circuito Wireworld con due anelli di clock, due diodi e una porta XOR, elettroni in blu e rosso su filo giallo — Due clock, due diodi e una porta XOR in Wireworld. Realizzato in PictorX.

Le 256 regole e le quattro classi di Wolfram

Una cella unidimensionale con due vicine vede uno di otto schemi, da 111 a 000. Una regola dà il nuovo stato per ciascuno di essi, quindi è fatta di otto bit, e ci sono 2⁸ = 256 regole elementari. Leggi le otto risposte come un numero binario e ottieni il nome della regola: la Regola 30 è 00011110 e la Regola 110 è 01101110. Stephen Wolfram ha ordinato le regole in base a ciò che fanno, dall’ordine al caos. 1. La classe 1 si assesta in uno stato uniforme. 2. La classe 2 si assesta in strutture stabili o ripetitive. 3. La classe 3 resta caotica e dall’aspetto casuale, come la Regola 30. 4. La classe 4 costruisce strutture che si muovono e interagiscono al confine tra ordine e caos, come la Regola 110.

Classifica per difficoltà

Gioco della vita ★☆☆☆☆ · Regola 30 ★☆☆☆☆ · Brian's Brain ★★☆☆☆ · Wireworld ★★★★☆ · Regola 110 ★★★★★. I primi due si spiegano da soli mentre li guardi. La Regola 110 nasconde le sue strutture mobili in uno sfondo ripetuto.

I più belli da vedere

1. Brian's Brain · 2. Gioco della vita di Conway · 3. Regola 30 · 4. Regola 110 · 5. Wireworld.

I più importanti in matematica

1. Regola 110, per l’universalità · 2. Gioco della vita, per l’universalità e l’emergenza · 3. Regola 30, per il caos e la casualità · 4. Wireworld, per la logica digitale · 5. Brian's Brain, per i sistemi eccitabili.

In natura, fisica e crittografia

Gli automi cellulari servono a simulare sistemi complessi in natura, fisica e crittografia. L’idea risale a Stanisław Ulam e John von Neumann negli anni 1940, che usarono una griglia di celle per progettare una macchina capace di copiare sé stessa. Nel mondo reale si vedono automi cellulari nel pigmento di alcune conchiglie, come il Conus textile, i cui triangoli somigliano alla Regola 30, e nelle squame della lucertola ocellata, che passano dal verde al nero secondo una regola vicina a un automa cellulare. I fisici li usano per modellare il flusso dei gas, i mucchi di sabbia e gli incendi boschivi. L’apparente casualità della Regola 30 l’ha resa una candidata per generatori di numeri casuali e cifrari a flusso.

Esplorali in PictorX

Apri Automi cellulari per avviarli tutti e cinque. Guarda il cannone di alianti, una flotta di astronavi o l’R-pentomino, che impiega 1.103 generazioni ad assestarsi. Digita qualsiasi regola di tipo Gioco della vita come B36/S23, o qualsiasi numero di regola elementare da 0 a 255. Disegna e cancella celle, invia elettroni nei circuiti Wireworld, collega i bordi e passa alla modalità colorata. Salva un PNG o apri la tela nell’editor PictorX.

Domande frequenti

Che cos’è un automa cellulare?

Una griglia di celle in cui ogni cella ha uno stato. A ogni passo tutte le celle si aggiornano insieme secondo un’unica regola fissa che guarda solo una cella e le sue vicine. Nonostante la semplicità delle regole, i motivi possono essere complessi e imprevedibili.

Chi ha inventato gli automi cellulari?

Stanisław Ulam e John von Neumann, negli anni 1940 a Los Alamos. Il Gioco della vita di John Conway (1970) rese popolare l’idea, e Stephen Wolfram studiò le 256 regole elementari negli anni 1980.

Quali automi cellulari sono Turing-completi?

Fra i cinque presenti qui, è dimostrato che la Regola 110 e il Gioco della vita sono universali, e Wireworld può contenere un computer completo. Universale significa che, con lo schema iniziale giusto, possono eseguire qualsiasi calcolo possibile per un computer generico.

Quali sono le quattro classi di Wolfram?

La classe 1 si spegne in uno stato uniforme, la classe 2 si assesta in strutture stabili o ripetitive, la classe 3 resta caotica come la Regola 30 e la classe 4 costruisce strutture mobili che interagiscono, come la Regola 110.

Perché la Regola 30 sembra casuale?

Ogni passo è stabilito, ma ogni cella mescola la vicina di sinistra con le altre due in un modo che diffonde rapidamente le piccole differenze. Nella sua colonna centrale non è stato trovato alcuno schema semplice, ed è per questo che è stata usata per generare numeri casuali.