Nella presentazione di questa panoramica sui CA, ci affideremo ad uno dei testi più esaustivi e meglio strutturati sull’argomento, mi riferisco al libro di Andrew Ilachinski, Cellular Automata. A Discrete Universe.109
Come abbiamo visto, a partire dalla pubblicazione dell’articolo di Turing del 1936 si è cominciato a delineare sempre meglio il concetto di processi computazionalmente irriducibili, ovvero che non esiste nessuna scorciatoia per predire il risultato di un programma arbitrario. Quasi cinque decenni dopo, Sthepen Wolfram, ha suggerito che questa proprietà dell’irriducibilità computazionale non è propria solo dei computer ma anche dei sistemi fisici reali.110
108Da ora in poi mi riferirò a questi modelli matematici con l’abbreviazione, CA. 109[Ila01].
L’origine dei CA è da far risalire ad uno degli studiosi che abbiamo già in- contrato parlando dei primi prototipi di computer, John Von Neumann, le cui ambizioni si spinsero fino a cercare un modello riduzionistico dell’evoluzione biologica.111 Il suo ambizioso programma era quello di astrarre un insieme
di interazioni logiche primarie necessarie per l’evoluzione di quelle complesse forme di organizzazione indispensabili per la vita, ma la sua intuizione più innovativa fu quella di usare un dinamica discreta, invece che continua, per costruire un automata bi-dimensionale che fosse capace di auto-riprodursi. Nonostante la sue complesse dinamiche e il suo ampio insieme di stati, il modello dei CA di Von Neumann rappresenta un altro primato, in quanto è stato poi dimostrato essere il primo modello discreto di computazione capace di computazione universale.
Ma cosa sono i CA? I Cellular Automata sono una classe di sistemi matematici deterministici ma che sono anche spazialmente e temporalmente discreti e sono caratterizzati da interazioni locali, queste caratteristiche li rendono estremamente versatili come prototipi di sistemi complessi e pro- cessi che coinvolgono un gran numero di componenti, semplici e identici, che interagiscono localmente. Lo studio di questi sistemi ha generato un grande interesse nella comunità scientifica nel corso degli anni, proprio per la loro capacità di generare un ampio spettro di complessi schemi, o patterns, di comportamento, a partire da un insieme relativamente semplice di regole sottostanti.
Mentre esiste un’immensa varietà di modelli CA particolari, ognuno cali- brato finemente per soddisfare i requisiti di uno specifico sistema, la maggior
parte di questi modelli condividono tutti queste cinque caratteristiche co- muni:112
• Reticolo discreto di cellule: il substrato di un sistema è costituito da un reticolo di cellule ad una, due o più dimensioni.
• Omogeneità: tutte le cellule sono uguali ed equivalenti.
• Stati discreti: ogni cellula prende uno tra un numero finito di possibili stati discreti.
• Interazioni locali: ogni cellula interagisce solamente con le cellule che sono nella sua immediata prossimità, o vicinato.
• Dinamiche discrete: per ogni unità discreta di tempo, ogni cellula aggiorna il suo stato attuale secondo delle regole di transizione che prendono in considerazione gli stati delle cellule nella suo vicinato. Vale la pena citare un passaggio dello stesso Ilachinski sulle caratteristiche dei CA:
C’è una semplicità ingannevole in queste caratteristiche. Ma nei fatti, [...] tali sistemi sono capaci di esibire un comportamento estremamente compli- cato. Per esempio, nonostante obbediscano regole locali e pur non avendo una scala di grandezza intrinseca altro che la dimensione del vicinato di cias- cun sito, i CA possono generare modelli [patterns] globali con un ordine e una correlazione di ampio raggio. I CA sono dinamicamente abbastanza ric- chi per essere presi seriamente in considerazione come modello matematico alternativo per una varietà di sistemi fisici.113
Per cogliere a pieno le potenzialità di questi sistemi, prenderemo in anal- isi due modelli CA che rappresentano sicuramente delle pietre miliari nello
112[Ila01], p. 5.
studio dei sistemi complessi, ovvero gli elementary CA114 e il Game of Life
di John H. Conway.115 Gli ECA sono i modelli matematici più semplici in cui
si considera il caso più semplice per gli stati del sistema e il vicinato di ogni cellula; limitandosi ad una sola dimensione gli ECA si svilupperanno in una sola dimensione, una serie unidimensionale di cellule, che sono limitate a due possibili stati, nero e bianco. Le regole di questi ECA determineranno come questa disposizione di cellule verrà aggiornata ad ogni stadio temporale. Ciò implica che per determinare lo stato di una cellula S(pi) al tempo t + 1, si
dovrà andare a vedere il vicinato, N(pi) := {pi−1, pi, pi+1} al tempo t e ciò
implica anche che lo stato di una cellula al tempo t, St(pi), sarà uguale ad
una funzione del vicinato di pi al tempo t − 1, ovvero: St(pi) := f (Nt−1(pi)).
Abbiamo a questo punto tutti gli strumenti che ci servono per generalizzare e cercare di capire il comportamento di questi sistemi, uno dei lavori più estensivi sull’argomento è senza dubbio il libro di S. Wolfram, A New Kind of Science.116
Nel caso degli ECA la griglia di cellule è sempre unidimensionale e og- nuna delle cellule può avere solo due stati possibili, questo significa che ogni vicinato sarà sempre composto da 3 cellule, quella centrale a cui si aggiornerà lo stato e le due limitrofe che lo determineranno a seconda delle regole scelte. Per analizzare il comportamento di questi sistemi, Wolfram ha proposto di adottare una convenzione per quanto riguarda la gerarchia dei possibili vici- nati. Ogni vicinato è composto da 3 unità che possono assumere due valori ciascuna, ciò implica che abbiamo 23 = 8 possibili combinazioni, la conven-
114Da ora in avanti mi riferirò a questi sistemi con l’abbreviazione ECA. 115[Gar70].
zione prevede di partire con il vicinato composto da tre cellule nere sulla estrema sinistra e finire con le tre cellule bianche sulla destra:117
Figure 6: Le otto possibili combinazioni delle tre cellule a due stati, nell’ordine conven- zionale stabilito da Wolram. [Wol85], p. 53.
Per ognuno di questi otto possibili vicinati, la cellula al centro potrà essere aggiornata in uno dei due stati possibili, e la definizione di questa funzione per ognuno dei vicinati sarà quello che determina le regole dell’automa. Uno dei possibili insiemi di regole è riportato nella fig. 7.
Figure 7: Un esempio di un set di regole ben definito per un ECA. [Wol85], p. 53.
Possiamo quindi notare come, tenendo fisso l’ordine dei vicinati possibili, otteniamo per ogni possibile vicinato, la cellula risultante da esso, il cui stato è definito dalla regola stessa. Ora considerando la sequenza di stati risultanti, essi identificano univocamente un numero binario il quale rappresenta il nos- tro insieme di regole. Ad esempio, per la fig. 7, otteniamo la seguente stringa binaria: 10010110. Ognuno di questi numeri binari rappresenta un numero anche nel sistema decimale, nel nostro caso 150, ed è proprio esso che è stato proposto da Wolfram come un modo ben definito di riferirsi ad un regola, come nell’esempio, la regola 150.
Non resta quindi che da considerare quante possibili combinazioni di re- gole ci possono essere e ci basterà applicare lo stesso procedimento già ap- plicato in precedenza. Non abbiamo altro che otto elementi i quali possono avere due possibili stati diversi, conseguentemente otteniamo 28 = 256 pos-
sibili regole diverse, ognuna rappresentante uno dei possibili ECA.118
Figure 8: Le prime tre regole e l’ultima. Il numero sulla destra è l’equivalente della regola nel sistema decimale. [Wol85], p. 53.
Le condizioni iniziali standard119 per tutte le regole consistono in una
singola cellula nera con solo cellule bianche che si estendono alla sua destra
118Vedi fig. 8.
119Queste condizioni sono state definite standard da Wolfram, [Wol85], il quale ha effet-
tivamente reso più semplice e comunicabile la classificazione dei vari ECA. Lo standard di visualizzazione sarà quindi di riportare le varie generazioni del CA una sotto all’altra, mentre la condizione di partenza più semplice sarà appunto una unica cellula viva al centro.
e alla sua sinistra.120 Per vedere le iterazioni multiple delle regole in una
sola volta ogni nuova generazione di cellule verrà rappresentata nella riga di cellule sottostante, mantenendo chiaramente la stessa posizione per ogni cel- lula della nostra griglia unidimensionale. Questo metodo di rappresentazione crea un’immagine bidimensionale delle successive iterazioni delle regole per ogni cellula che permette un’analisi del loro comportamento, vedi la fig. 9 per alcuni esempi.
Figure 9: Evoluzione di diversi ECA con una sequenza di diverse possibili regole da condizioni iniziali standard. [Wol85], p. 54.
Wolfram ha classificato il comportamento manifestato da questi sistemi in quattro classi differenti:121
120Lo studio si può chiaramente estendere a tutti i tipi di condizioni iniziali, ma questo
complica il quadro e per semplicità espositiva ometteremo questo dettaglio.
Classe I contiene quei sistemi con un comportamento semplice e ripet- itivo, che può variare da una linea verticale o diagonale (come nelle re- gole 100, 106, 108, 112...), a una serie alternata di cellule tutte bianche o nere (come nelle regole 113, 115, 117, 119...). Approssimativamente l’86% degli ECA è di questo tipo.
Classe II viene caratterizzata da quei ECA che contengono nested patterns, o strutture annidate, vale a dire delle configurazioni che si ripetono in se stesse in una qualsiasi scala più grande. Questo è anche ciò che tipicamente ci ricorda il tratto fondamentale delle strutture frattali. Questa tipologia ammonta al 9% circa.
Classe III si contraddistingue per contenere tutti quei sistemi che es- ibiscono un comportamento random. Anche se questi ECA contengono strutture che si ripetono al loro interno, la loro frequenza e posizione rimane comunque random.122 Questa classe contiene circa il 4% degli
ECA.
Classe IV risulta essere una sorta di combinazione tra la classe I e III; questi ECA comprendono una complessa combinazione di schemi ripetitivi e comportamento randomico.123 Ci sono solo quattro sistemi
che esibiscono questo comportamento, e tutti e quattro sono fonda- mentalmente equivalenti se si considerano le simmetrie bianco/nero e destra/sinistra.
122Vedi fig. 10, per un esempio di ECA della terza classe. 123Vedi fig. 11, per un esempio di ECA della quarta classe.
Figure 10: Le prime centocinquanta iterazioni della regola 30.
Figure 11: Le prime cento iterazioni della regola 110.
Questa classificazione ci risulterà utile nelle prossime sezioni quando an- dremo a considerare la portata computazionale degli ECA. Inoltre, nonos- tante la classificazione sia basata solo su un riconoscimento visivo di deter- minati schemi e caratteristiche, è precisamente questo che Wolfram ritiene essere uno dei fattori fondamentali nella determinazione dei livelli di comp-
lessità.
Possiamo adesso passare ad analizzare il secondo esempio di CA che, senza dubbio, ha fatto scorrere fiumi di inchiostro dalla sua prima comparsa nel 1970 su Scientific American: il Game of Life, o gioco della vita, di Conway.124
Questo modello di CA è basato su una griglia a due dimensioni, in cui ogni cellula continua ad avere solo due stati possibili: vivo o morto. Il vicinato di ogni cellula sarà quindi composto da ben otto vicini e, ad ogni generazione, una determinata cellula sarà viva o morta in accordo con le seguenti regole: • nascita sostituire una cellula morta con una viva se ci sono esatta-
mente tre vicini in vita.
• morte sostituire una cellula precedentemente in vita, con una morta se i) la cellula in vita ha non più di un vicino vivo (morte per soli- tudine); o ii) la cellula vivente ha più di tre vicini in vita (morte per sovrappopolazione).
• sopravvivenza le cellule si mantengono in vita se hanno esattamente due o tre vicini in vita.
Nonostante questo insieme di regole sia così semplice e minimalista, questo modello CA si è rivelato capace di esibire comportamenti complessi al di là di ogni possibile immaginazione. Uno degli schemi più intriganti che emergono da questo sistema è senza dubbio quello del glider.125
Rappresentato nella prima immagine a sinistra nella fig. 12, un glider consiste di cinque cellule ‘vive’ e riproduce se stesso diagonalmente in una
124[Gar70]. 125Vedi fig. 12.
Figure 12: Lo schema di un glider nel gioco della vita.[Ila01], p. 14.
posizione successiva ogni quattro iterazioni. Quando i vari stati delle sin- gole iterazioni vengono proiettate in rapida successione su uno schermo da un computer, questi glider danno l’impressione di camminare attraverso lo schermo. La propagazione di queste strutture quasi-stabili può essere visto come una proprietà emergente del nostro sistema. Non c’è traccia in nes- suna dei gliders nelle regole, che non sono definite né implicitamente, né esplicitamente in termini di essi. Inoltre i gliders non sono generati esplicita- mente, ovvero, non esiste un algoritmo dei glider. Il che equivale a dire che non abbiamo un codice, un programma che ci possa decidere esplicitamente quali cellule dovrebbero essere accese e spente per creare un glider, il che ci rimanda subito alla complessità intrinseca del sistema.
A conclusione di questa introduzione ai CA vorrei riproporre al lettore una delle domande fondamentali a cui Ilachinski cerca di rispondere nel suo libro: «Perché è fondamentale studiare i CA? »La risposta a questa domanda viene trovata identificando almeno quattro ragioni parzialmente interconnesse, le quali vengono presentate secondo il loro ordine di rilevanza teoretica.126 I
CA possono essere quindi visti come: CA1 potenti motori di calcolo
CA2 simulatori di sistemi dinamici discreti
CA3 strumenti concettuali per studiare la complessità
CA4 modelli originali della fisica fondamentale
Non ci andremo ad occupare di tutti questi aspetti in quanto non rientrano negli obiettivi di questo testo. Tuttavia andremo ad approfondire la prima caratteristica che, non a caso, è anche quella di portata teoretica più ampia, ovvero la capacità dei CA di poter operare e manipolare informazioni in modo analogo ad un computer moderno.
5.3.1 La soglia dell’universalità
Ciò che risulta più notevole del sistema di Conway, che, come abbiamo visto nella precedente sezione, è costituito da regole molto semplici, è la possibilità di dimostrare che esso è equivalente ad un calcolatore universale, ovvero ad una macchina di Turing universale. Ciò significa che con una scelta adeguata delle condizioni iniziali, la distribuzione iniziale di cellule vive o morte, il gioco della vita può essere trasformato in un computer con scopi generici. Questo fatto implica anche che esistono dei limiti fondamentali alla prevedibilità del sistema stesso. Il famoso teorema del problema dell’arresto, o Halting The- orem, che vale per le macchine di Turing universali si applica quindi anche al nostro Game of Life. Infatti, visto che esso è equivalente ad un computer universale, ciò implica che non possiamo, in generale, predire se una deter- minata configurazione iniziale di cellule porterà o meno all’estinzione, ovvero
tutte le cellule ad un certo punto saranno solo bianche. Ciò che ci inter- essa sottolineare qui è che non c’è nessuna scorciatoia possibile, nemmeno in principio; tutto ciò che ci rimane da fare, per quanto poco soddisfacente, è di aspettare pazientemente il risultato finale dello modello stesso del gioco della vita. In sintesi, il Game of Life, come tutti i sistemi computazional- mente universali, definisce implicitamente la più efficiente simulazione del suo stesso comportamento.127
Il concetto di computazione universale implica che una volta ottenuto un certo livello di complessità, non ci possono essere altri guadagni da un punto di vista di potenza di calcolo. Questo fatto è di per sé implicato dall’abilità delle macchine di Turing universali di poter simulare il comportamento di altre macchine con tabelle, o programmi, più complessi dei propri. Il livello di complicatezza128 al quale si raggiunge l’universalità di calcolo viene definita
la ‘soglia dell’universalità’, o Treshold of Universality. Intuitivamente si è sempre pensato, a partire dalla rivoluzione informatica, che questa soglia fosse molto alta; ovvero, si era implicitamente assunto che una macchina capace di poter eseguire calcoli così complessi dovesse essere, o fatta di parti complesse, oppure di parti semplici ma messe insieme in un modo complesso. Un risultato che senza dubbio ha rappresentato una sorpresa per gli studiosi della complessità, è stato quello presentato da Wolfram in A New Kind of Science. Wolfram dimostra che uno dei 256 ECA, ovvero uno dei più semplici cellular automata è anch’esso capace di computazione universale, si tratta del
127[Ila01], p. 15.
128Per non confondersi con un uso più specifico e profondo di complessità, sul quale ci
sistema ECA con la regola 110.129 In effetti questa soglia dell’universalità si
rivelata essere sorprendentemente bassa.
Nonostante l’ECA 110 sia l’unico sistema portato come esempio in questa sede, esistono molti altri tipi di macchine e programmi, anche nel libro di Wolfram, che esibiscono la capacità di computazione universale, rimanendo tuttavia allo stesso livello di semplicità degli ECA. Quasi tutti questi esempi ricadono all’interno della classe IV mentre una piccola parte rientra nella classe III.
Il concetto di soglia dell’universalità, insieme ad un ampio numero di importanti similarità tra programmi semplici e sistemi naturali, stanno alla base del principio di Wolfram dell’equivalenza computazionale o Principle of Computational Equivalence.130. Questo principio teorico si fonda su un
concetto chiave: che tutti i processi, sia che siano prodotti da uno sforzo umano o che avvengano naturalmente, possono essere visti come forme di computazione. I modelli CA, come anche altri programmi simili, non solo sono capaci di raggiungere il livello di complessità rilevato nei processi nat- urali spontanei ma presentano anche delle similarità stupefacenti. Vedi ad esempio le fig.13 e fig. 14.
Sia i sistemi naturali che i programmi esibiscono quindi delle similarità di comportamento, mentre differiscono significativamente per la struttura sot- tostante e la loro base biologica; Wolfram cerca di spiegare e interpretare queste similarità di comportamento in termini di computazione.
La seconda parte del PCE asserisce che tutti i sistemi che non appaiono
129Vedi, Fig. 10, sez. 5.3.
Figure 13: Somiglianza tra ECA regola 18 con delle condizioni iniziali puramente random e il pattern di una conchiglia di mare.
Figure 14: Sulla sinistra, immagine a), vediamo un fiocco di neve; mentre a destra, b), abbiamo la rappresentazione della ventiquattresima iterazione di un CA esagonale. Le regole di trasformazione permettono ad una cellula bianca di diventare nera solo se una cellula nel suo vicinato è nera. Altrimenti la cellula bianca rimane bianca.[Wol85], pp. 370-371.
semplici, in maniera ovvia ed evidente, sono tutti di equivalente sofisticatezza computazionale. Il che vale a dire, secondo Wolfram, che tutti i sistemi nel nostro universo che esibiscono comportamenti della classe III e IV, sono com- putazionalmente universali e quindi fondamentalmente equivalenti. Se tutto ciò che un sistema fa è di computare il suo stesso comportamento, ed esso è anche computazionalmente universale, allora può riprodurre il comporta- mento di qualsiasi altro sistema e conseguentemente tutti questi sistemi sono
perciò equivalenti.
Il principio di equivalenza computazionale postulato da Wolfram ha delle profonde implicazioni per praticamente tutti i campi di indagine scientifica e sociale. Se il PCE si rivelasse vero, si potrebbe già sperare che usare CA o altri programmi simili per modellare i processi naturali sia un procedimento destinato al successo, tuttavia ritorna a farsi sentire uno dei concetti fonda- mentali che abbiamo analizzato nella sez. 3.2, quello dell’irriducibilità che, a questo punto, si ripresenta ai nostri occhi nella sua forma computazionale. Ciò implica che il comportamento di programmi non banali non può essere ridotto ad una forma più semplice di computazione, come ad esempio una formula matematica. Essenzialmente questo significa che non esiste nessuna formula che può predire il comportamento di un sistema ad ogni unità di tempo senza essere tanto computazionalmente complessa quanto lasciare che il sistema calcoli il suo stesso comportamento.
In sostanza, tutti i sistemi che sono complessi a sufficienza da oltrepas- sare la soglia dell’universalità, sono automaticamente computazionalmente irriducibili. Ciò che vale la pena sottolineare è che come le formule per ri- cavare la serie di cifre decimali di π sono in un certo senso versioni compresse di π, le leggi della fisica, sulle quali facciamo così tanto affidamento e delle quali ci sentiamo pienamente padroni, possono essere viste come sistemi che