Introduzione agli automi cellulari

Che cosa è un automa cellulare?

Un automa cellulare è un sistema dinamico discreto. Possiamo pensare a un automa come a un universo stilizzato in cui:

• lo spazio è rappresentato da una griglia uniforme, ogni cella (o individuo) può assumere un certo numero finito di stati;
• il tempo avanza a passi discreti;
• le leggi dell'universo dicono come cambia (ad ogni passo) lo stato di ogni cella a seconda dello stato delle celle che le stanno intorno.

Caratteristiche essenziali

• Spazio, tempo e stati sono discreti;
• le leggi sono uniformi, cioè uguali per tutte le celle;
• le leggi sono locali, cioè dipendono solo dalle celle vicine;
• il tempo avanza simultaneamente per ogni cella.

Costruiamo il nostro automa

Per creare il nostro universo dobbiamo scegliere:

• la griglia (può essere lineare, quadrata, esagonale, infinita o chiusa);
• i possibili stati (ad esempio due o tre colori);
• il vicinato;
• le leggi di evoluzione.

L'evoluzione dell'automa

Scegliamo una configurazione iniziale, cioè ad ogni cella assegniamo uno stato. Lasciamo evolvere l'automa per un certo tempo. Che cosa può succedere?

• Si arriva a una configurazione finale stabile.
• Il sistema continua a evolvere all'infinito in un modo regolare.
• Il sistema continua a evolvere all'infinito in modo non regolare (caotico).

Il gioco LIFE

Un esempio di automa cellulare inventato dal matematico John Conway nel 1970 è il gioco Life.

• La griglia è bidimensionale quadrata e chiusa;
• gli stati sono due: vivo-morto (nero-bianco);
• il vicinato è costituito dalle otto celle vicine;
• le leggi sono: una cella viva resta viva solo se ha 2 o 3 celle vive vicine, una cella morta diventa viva se ha esattamente 3 celle vive vicine.

Le applicazioni

Gli automi cellulari danno una rappresentazione immediata e semplice di fenomeni in cui l'evoluzione globale dipende da leggi locali. Alcuni esempi sono:

• il comportamento fisico dei gas perfetti;
• l'evoluzione di una popolazione sotto l'effetto di leggi economiche e sociali;
• la diffusione di una malattia infettiva all'interno di una popolazione
• la crescita di un organismo vivente;
• l'evoluzione di un ecosistema;
• fenomeni di fluidodinamica;
• fenomeni di riscaldamento e turbolenze.

Link utili e di approfondimento

• Automi unidemsionali
• Il gioco Life
• Altre vite
• Game of Life (applet Java ed eseguibili per Windows, Mac e Linux)