| 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 di studiare i loro meccanismi comportamentali. 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 modello formale formato di
celle come
dice il suo stesso nome.
Gli automi cellulari sono essenzialmente
caratterizzati 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. La varietà delle regole di transizione
1. La geometria della matrice delle celle può essere
bidimensionale tridimensionale o multidimensionale (a n dimensioni).
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 prendono una precisa
configurazione (reticolare, lineare ecc.) e danno la topologia dell'automa.
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 detta 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.
Poiché il tema è
alquanto complesso come esempio introduttivo prendiamo 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 tre bit
che danno otto combinazioni in tutto, cioè le situazioni iniziali sono
otto. La funzione di
transizione indica lo stato che x dovrà acquisire per ognuna delle terne
possibili, dunque la
funzione viene facilmente illustrata da una tabella del tipo in
figura.
|
111
|
110
|
101
|
100
|
110
|
010
|
001
|
000
|
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
0
|
Ad esempio, 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. Mediante
specifici calcoli si prevede il comportamento dell'automa nel tempo. Ad
esempio si scopre se arriverà mai ad
una configurazione stabile oppure no. Gli
automi cellulari hanno una importanza sul piano teorico. Basta dire che la
macchina di Turing è un tipo speciale di automa. Hanno
un'importanza pratica forse maggiore perché simulano il comportamento di
sistemi complessi come quelli biologici e 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 i comportamenti degli esseri viventi possono emergere da regole semplici
e da
interazioni di molti corpi, principio che è alla base dell'ecobiologia. Del gioco,
diventato popolare, ne furono sviluppate versioni con differenti topologie,
differenti regole
biologiche, e differenti tipi di celle.
Indietro
|