Il concetto di automa cellulare
fece la sua comparsa
nell’ambiente scientifico verso la fine degli anni 40 allorché Stanislaw Ulam (1909-1984) e
John von Neumann (1903-1957) si proposero di sviluppare modelli matematici
di fenomeni complessi come
quelli biologici, in particolare intendevano studiare i loro meccanismi
comportamentali di un alto numero di entità. Negli anni 70 Burks e John Conways ampliarono notevolmente
i risultati iniziali. Nel decennio successivo emerse il contributo di
Stephen Wolfran.
Tutt'oggi l'automa
cellulare è al centro di significative indagini poiché tocca svariati
settori teorici e pratici.
L'automa cellulare è
un sistema formato di
celle come
dice il suo stesso nome.
Esse sono essenzialmente
caratterizzate da quattro proprietà:
1. La geometria della matrice delle celle
2. L’intorno o vicinato di ogni cella
3. Il numero di stati per cella
4. Le regole di transizione.
Vediamo in dettaglio:
1. La geometria della matrice delle celle può essere
bidimensionale, tridimensionale o multidimensionale.
2. L’intorno di una cella comprende le celle fisicamente adiacenti oppure
le celle determinate tramite una funzione metrica (distanza) definita
nello spazio delle celle. Le
celle che interagiscono danno una precisa topologia all'automa che è
reticolare, lineare ecc.
3. In ogni istante la cella x assume un preciso stato (es. 0 oppure 1) il quale dipende
dallo stato precedente di x e dallo stato delle celle vicine ad x.
4. Gli stati di tutte
le celle cambiano secondo un’unica legge, descritta da una funzione di transizione che segue di solito criteri di vicinanza. In altri termini
a determinare il cambiamento dello stato di una cella contribuisce lo stato corrente della cella stessa, nonché quello assunto da prefissate celle, legate
secondo una relazione di vicinato.
Il discorso forse appare
alquanto astruso, per chiarire i punti sopra riportati facciamo il caso più
semplice possibile.
Supponiamo che l'automa sia lineare ed abbia il
raggio minimo
che è 1, cioè lo stato della cella x dipende dalla
cella (x-1) e dalla cella (x+1). Gli stati di (x-1), x ed (x+1) sono dati
da tre bit
che danno otto combinazioni in tutto. La funzione di
transizione indica lo stato che x dovrà acquisire per ognuna delle terne
possibili, dunque la
funzione viene facilmente illustrata dalla seguente
tabella di transizione
bidimensionale.
|
111
|
110
|
101
|
100
|
110
|
010
|
001
|
000
|
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
La tabella si legge nel seguente modo. La prima
colonna dice che se (x-1), x ed (x+1)
si trovano tutte e tre nello stato 1, allora x assumerà lo stato 0. La
seconda colonna dice che se (x-1) ed x sono 1 ma (x+1)
è 0 allora x assumerà lo stato 1e così via. Supponiamo che l'automa sia circolare ed abbia 5
elementi. All'inizio immaginiamo che i primi tre elementi - cioè (x-1), x
ed (x+1) - siano pari ad 1. Gli elementi successivi sono due
zeri:
11100
Ciò vuol dire che si parte dalla configurazione riportata nella prima
colonna la quale produce l'elemento x pari a 0:
10100
Al secondo step si considerano gli elementi 010 i quali dalla sesta colonna
della tabella producono il seguente risultato:
10000
Ora si evolvono gli ultimi tre elementi dell'automa i quali l'ultima colonna
della tabella dice che devono produrre 1:
10010 Poiché il
sistema è circolare gli ultimi due elementi di destra in realtà sono
contigui al primo a sinistra. Questa terna si evolve con le regole di
transizione in tabella. Poi toccherà all'ultimo elemento a destra con i due
a sinistra, dopo si ritorna alla terna vista all'inizio e via di seguito
passo dietro passo. Mediante specifici programmi gli esperti prevedono il
comportamento dell'automa nel tempo, cioè quello che succede dopo moltissimi
cicli sulla base della funzione di transizione. Ad esempio è importante
scoprire se l'automa arriverà mai ad una comportamento stabile, ovvero gli
stati delle celle non mutano più oppure variano di poco. Gli
automi cellulari hanno una importanza sul piano teorico. Basta dire che la
macchina di Turing è un tipo speciale di automa. Gli automi cellulari
hanno
un'importanza pratica ancora maggiore perché simulano il comportamento di
sistemi complessi come quelli sociali difficilmente
trattabili in altro modo. Facciamo il caso della
folla che ha sentito lo scoppio di una bomba ed è in preda al panico:
Cosa farà la folla impazzita?
Il comportamento complessivo dipende da ciascun individuo il
quale è simile ad una cella che regola il suo agire rispetto a quelle
che gli stanno intorno. Cioè, grazie agli automi cellulari, si riconduce un fenomeno
complicatissimo in termini molto più semplici da calcolare. Prima
di chiudere va ricordato "il gioco della vita (Game of Life)",
sviluppato da Conway sul finire degli anni '60, con lo scopo di mostrare
come dal comportamento degli esseri viventi possono emergere regole semplici
dovute all'interazione del singolo individuo con i vicini, regole che sono
alla base dell'ecobiologia. Del gioco,
diventato popolare, ne furono sviluppate versioni con differenti topologie,
differenti regole
biologiche, e differenti tipi di celle.
anno 2005 |