Esempio di sviluppo di un automa cellulare totalistico ( TCA )
Quante volte avete sognato di essere degli Dei? Quante volte avete pensato di poter amministrare un universo in miniatura, un sistema regolato dalle vostre regole, simulandone gradualmente la progressione e lo stato finale. Nei primi anni 50 due matematici di nome Stanislaw Ulam e John Von Neumann ( al secondo si deve un particolare merito per lo sviluppo di teorie e tecniche che hanno reso l’informatica moderna ciò che è in questo momento ) partorirono l’idea di Automa Cellulare: un organismo in grado di riprodurre sè stesso e svilupparsi nel corso del tempo secondo regole prestabilite dal creatore. Lo scopo e l’utilità di queste risorse sono lapalissiani: è possibile descrivere, analizzare e far progredire un algoritmo simulante il comportamento di una data entità, per esempio il Conus ( un mollusco gasteropode marino presente nel Mar Mediterrano ) deve la colorazione del suo involucro ad un motivo ( pattern ) generato tramite un automa cellulare naturale. Nella teoria dei sistemi si può vedere un automa cellulare come un descrittore di un sistema complesso, ovvero un sistema composto da unità ( sistemi semplici ) che acquisisce input e reagisce a questi a seconda di ciò che è presente nell’ambiente circostante restituendo un output variabile ma calcolato mediante una serie di passaggi definiti da regole e una transizione di stato. Per avere un esempio autoesplicativo di sistema complesso pensiamo ad un alveare, composto da api che si muovono nel tempo facendo ciò che serve alla intera comunità e cambiando singolarmente la totalità dell’organismo del sistema.
Nella teoria dei sistemi per descrivere automi si utilizza solitamente una notazione in quadruple o quintuple. Possiamo riassumere il funzionamento e i requisiti di un automa cellulare con una quadrupla: [math]( d, Q, N, f )[/math]
L’evoluzione dell’automa è dovuta ad una unica funzione definita, detta funzione di transizione, applicata ad ogni cella in ogni momento di sviluppo.
Esistono, ovviamente, molte varietà di modelli di automi cellulari, vediamo i principali:
Sono il tipo di AC più vicino a quello standard. Sono semplicemente una astrazione del modello standard avendo una diversa funzione di transizione che genera [math]2^S[/math] stati possibili e una funzione di transizione globale che ritorna uno dei possibili casi degli stati calcolati in modo non deterministico dalla funzione di transizione descritta precedentemente. L’equazione di transizione è la seguente: [math]{[tau(c)](i)varepsilon} {sigma(c(N(X,i)))}[/math]
Sono molto simili agli AC non deterministici ma il loro scopo è quello, come da nome, di simlare fenomeni probabilistici, per esempio la natura ondulatoria della materia o l’andamento dei gas reticolari. Nel caso degli AC ogni cella è configurata in modo da calcolare la probabilità di ogni possibile movimento della cella movente. L’equazione di transizione è la seguente: [math]sigma : S^n times S rightarrow [(0;1)][/math]
Anche questi sono una modifica al modello standard, questo tipo particolare di AC al posto di calcolare il nuovo stato di posizione dipendentemente da tutti gli stati di tutte le celle vicine legge solo la componente i-esime dello stato della cella i del suo vicinato. L’equazione di transizione è la seguente: [math] sigma : S_{k1} times S_{k2} dots S_{kn} rightarrow S_{k1} times S_{k2} dots S_{kn}[/math]
In un AC asincrono ad ogni passo dello sviluppo del sistema una cella può decidere in maniera non deterministica se mantere il proprio stato costante dunque [math]S_{0} = S_{-1}[/math] oppure applicare la funzione di transizione [math]sigma : S^n rightarrow S[/math]. La funzione di transizione globale è la seguente: [math][ tau (c)](i) = sigma (c(N(X,i))) vee [ tau (c)](i) = c(i)[/math]
Gerarchico ( o multilayered ) è un automa cellulare non minimale, ma è scindibile in parti più semplici da cui dipende lo stato finale della cella in esame. La struttura di un multilayered AC è appunto gerarchica, composta dunque da n layers con [math]N = { 0, 1, dots, max }[/math]. L’ambito di utilizzo di questi sistemi è lampante: la simulazione di sistemi bioligi a strati.
Nel campo degli automi cellulari ce ne sono tre che hanno particolarmente attirato la mia attenzione. Il primo sicuramente lo conoscerete, lo conoscono quasi tutti gli informatici direttamente o indirettamente, il suo nome è Gioco della Vita ( dall’inglese Game of life ). Il Life è un automa cellulare che descrivere comportamenti simili ad organismi viventi dettati da regole di interazioni base dell’ecobiologia e della teoria della complessità Lloyd. Il suo creatore, il celeberrimo matematico inglese John Horton Conway, creatore del metodo Doomsday e noto ricercatore.
Le regole del Life sono semplici ma sensate, data una matrice MxN di celle quadrate che rappresenta il mondo, ogni cella ha otto vicini rappresentata dalle celle adiacenti ( incluse quelle diagonali ).
Una cella può avere due stati, dunque [math]S = {0,1}[/math] dove 0 è alias di morto e 1 è alias di vivo. La sopravvivenza di un individuo è regolata da battiti regolari di intervallo da noi definito lungo la linea temporale. Importante dire che tutte le celle debbono essere esaminate nella totalità tra un battito ed un altro per causare una generazione di massa. Quando una cella morta ha esattamente 3 vicini vivi nasce diventando viva, quando una cella ha dai due a tre vicini sopravvive, se ne ha meno di 2 muore per isolamento e se ne ha più di 3 muore per sovraffollamento.
Sicuramente tratterò più approfonditamente del Game of Life in seguito in un altro articolo, mostro in basso un esempio di Cannone di Gosper, ovvero una combinazione da cui si parte e che rimane infinita per la totalità del tempo:
Cannone di Gosper
Seguono alla lista degli automi cellulari interessanti anche Wa-Tor e la Formica di Langton.
Conclusioni
Trovo l’argomento Automi Cellulari molto sottovalutato e ignorato, ma a mio parere rimane uno degli argomenti più interessanti dell’informatica dato che riunisce matematica, teoria dei sistemi e informatica. Simulare un qualcosa che può essere lontanamente paragonato alla vita è un’idea inebriante e magnifica. Scriverò sicuramente altri articoli sull’argomento e potrò ampliarli anche con informazioni su intelligenza artificiale e algoritmi genetici, grazie dell’attenzione.
Per qualsiasi riferimento scrivetemi su Twitter ( @_darklotus ) o via email [email protected].
