Umberto Cerruti

Dipartimento di Matematica, Università di Torino

Si assiste ad una progressiva matematizzazione della Biologia, con una interazione reciproca tra le due discipline simile per ricchezza di risultati a quella classica Matematica - Fisica.

In questo articolo si tratta brevemente di alcuni modelli di apprendimento (reti neurali) e di alcuni modelli evolutivi di vita artificiale (automi cellulari).

In entrambi i casi si evidenzia un approccio acentrato e locale alla conoscenza della natura.

L'idea di rete neurale ha la sua origine nell'avvento di una nuova tecnica di colorazione, inventata dall'istologo italiano Camillo Golgi intorno al 1880, che permetteva di rivelare nei minimi dettagli la struttura delle fibre nervose.

Il medico spagnolo Santiago Ramon y Cajal perfezionò il colorante di Golgi e riuscì nel 1889 a provare al di là di ogni dubbio l'ipotesi avanzata nel 1888 dall'anatomista tedesco H. W. Gottfried von Waldeyer-Hertz, il quale fu il primo a sostenere che il sistema nervoso è formato da cellule separate, dette neuroni.

Da ogni neurone si dirama un assone (una fibra nervosa) che giunge vicinissimo ad altri neuroni senza però toccare i loro dendriti (ramificazioni di ingresso) o il loro corpo centrale. La congiunzione avviene attraverso una sottile fessura, detta sinapsi.

E' proprio l'esistenza delle sinapsi che permette di considerare il sistema nervoso come un insieme di numerose unità interconnesse.

I neuroni comunicano tra di loro attraverso processi elettrochimici assai complessi.

Ogni neurone riceve come input segnali di eccitazione o di inibizione da molti altri (a volte decine di migliaia); in risposta ad essi elabora un output costituito da un singolo impulso elettrico che si propaga lungo l'unico assone che si diparte dal suo nucleo.

L'idea è dunque: tanti input - un output; naturalmente questo unico output può essere comunicato a molti altri neuroni.

Il primo esempio di neurone artificiale fu quello di McCulloch e Pitts (1943).

Questo neurone è un'unità binaria che può fornire come output i valori 0 o 1. Possiede input eccitatori e inibitori (simulando ciò che avviene in alcuni casi nelle connessioni neurali biologiche). Se almeno un input inibitorio è attivato (cioè vale 1) l'uscita è 0. Altrimenti l'unità calcola la somma S degli input eccitatori (ognuno di loro ha valore 0 o 1); se S supera un certo valore di soglia l'uscita è 1, in caso contrario è 0.

Questi neuroni molto semplici si possono connettere tra di loro, formando reti neurali.

McCulloch e Pitts provarono che queste reti possono simulare una macchina di Turing universale, vale a dire che esse hanno le stesse capacità di calcolo di un moderno computer.

Queste macchine sono dunque in grado di eseguire qualsiasi algoritmo finito; però - per limitazioni dovute alla loro stessa struttura - non possono apprendere nulla di nuovo, al contrario dei sistemi biologici.

La scoperta del primo neurone artificiale in grado di apprendere (detto perceptrone) è generalmente attribuita allo psicologo americano F. Rosenblatt (1958).

Per spiegare il funzionamento del perceptrone nel modo più efficace useremo una notazione vettoriale.

Il neurone possiede n+1 input:

Pensiamo ad essi come componenti di un vettore di input X.

Per ogni input è fissato un peso sinaptico:

Assumiamo i pesi come componenti di un vettore sinaptico W.

L'uscita è data da:

dove F è la funzione di attivazione, eventualmente non lineare.

Utilizzando la notazione vettoriale l'output è dunque:

F (XW)

dove, naturalmente, XW rappresenta il prodotto scalare del vettore di input e del vettore sinaptico.

La prima componente di X (quella di indice 0) è posta uguale a -1. Questa ed il relativo peso sinaptico q (detto bias) rappresentano il valore di soglia.

Supponiamo, per esempio (come nel modello di Rosenblatt), che F sia la funzione segno: F (z) =1 se z > 0, F (z) = - 1 se z £ 0.

Se n = 2 e q = 0.2 allora dato W = [0.2, 2, -1] in corrispondenza dell'input [-1, a, b] si avrà l'output 1 se 2a - b > 0.2, e l'output - 1 se 2a - b £ 0.2.

In questo caso l'input effettivo è dato dalla coppia [a, b] ed il valore di bias è 0.2.

Rosenblatt dimostrò che il perceptrone è in grado di apprendere modificando i propri pesi sinaptici .

Predisponiamo una successione (finita) di coppie di apprendimento [X(t),y(t)], dove t=0,1,2…, X(t) è un vettore di input e y(t) è la risposta che noi vogliamo in corrispondenza di X(t).

W(0) è il vettore iniziale dei pesi sinaptici (casuale).

Se F (XW) è uguale a y(t) non cambiamo nulla, altrimenti poniamo W(t+1) = W(t) + h y(t)X(t), dove h è il coefficiente di apprendimento (numero reale positivo).

Allora se esiste una soluzione si prova che in un numero finito di passi i pesi si saranno aggiustati in modo da dare per ogni input la risposta desiderata (vi sono generalmente infinite soluzioni).

Può essere necessario presentare l'insieme delle coppie di apprendimento più volte, in ordine arbitrario. La regola di apprendimento proposta da Rosenblatt per il suo perceptrone è analoga (anche se più potente) a quella individuata nel 1949 dallo psicologo canadese D. O. Hebb.

Secondo questa regola viene rafforzata la connessione sinaptica tra due neuroni se essi sono simultaneamente attivi. Nel modello di Rosenblatt la componente i-esima del peso sinaptico aumenta se la componente i-esima dell'input e l'output hanno lo stesso segno.

Il fatto che reti neurali artificiali fossero in grado di apprendere destò grande eccitazione tra gli addetti ai lavori ed anche all'esterno, per cui negli anni 60 vi furono molte ricerche in questo campo. Tutto questo entusiasmo però ricevette un duro colpo nel 69.

M. Minsky e S. Papert scrissero un libro sul perceptrone, evidenziandone i limiti.

Per comprenderli soffermiamoci sull'apprendimento di funzioni booleane. Seguendo Rosenblatt identifichiamo vero con 1 e falso con -1; allora una n-upla di valori vero-falso si può considerare un vertice dell'ipercubo n-dimensionale centrato nell'origine con spigoli di lunghezza 2.

Per esempio per n=2 abbiamo il quadrato:

(-1,1) (1,1)

(-1,-1) (1,-1)

Una funzione booleana è allora una funzione che ad ogni vertice dell'ipercubo associa 1 o -1 (cioè vero o falso, nella nostra interpretazione).

Una funzione booleana si dice linearmente separabile se l'insieme dei vertici dell'ipercubo ove assume il valore 1 può essere separato dall'insieme dei vertici in cui assume il valore -1 da un iperpiano.

Per esempio, con n=2, la funzione AND (congiunzione) definita da:

AND(-1,1) = -1, AND(1,1) = 1, AND(-1,-1) = -1, AND(1,-1) = -1,

è linearmente separabile; si noti che in questo caso l'iperpiano è semplicemente una retta che separa il vertice di coordinate (1,1) dai rimanenti tre.

Invece la funzione XOR (disgiunzione esclusiva) definita da:

XOR(-1,1) = 1, XOR(1,1) = -1, XOR(-1,-1) = -1, XOR(1,-1) = 1,

non è linearmente separabile.

Uno dei risultati contenuti nel libro di Minsky e Papert è che soltanto le funzioni booleane linearmente separabili possono essere apprese dal perceptrone.

Dunque una funzione così elementare come lo XOR non può essere insegnata alla macchina di Rosenblatt!

Questa e altre critiche espresse dagli autori - studiosi autorevoli inseriti in gruppi di ricerca di grande prestigio - furono sufficienti ad estinguere, almeno pubblicamente, le ricerche sulle reti neurali per più di un decennio.

Nel 1960 B. Widrow e M.E. Hoff introdussero la cosiddetta regola delta, che descriviamo senza entrare in troppi dettagli, nel caso di un solo neurone di uscita.

Dato il nostro insieme di coppie di apprendimento [X(t), y(t)], e dato un vettore sinaptico W, applicando l'input X(t) non otterremo generalmente l'uscita desiderata y(t) ma un output diverso o(t), dove - come sopra - o(t) = F (X(t)W).

Possiamo allora considerare l'errore quadratico complessivo, sommato su tutte le coppie, come una funzione E di W:

Se F e differenziabile allora lo è anche E, e si ottiene così una superficie dell'errore sulla quale si possono cercare i minimi, per esempio con il metodo del gradiente.

Dato cioè W, lo si sostituisce con W + D W, dove D W è scelto in modo tale da muoversi sulla superficie dell'errore nella direzione di più ripida discesa (di qui il nome regola delta).

Si prosegue finché si trova W tale che l'errore E(W) è al di sotto di un certo limite, dato dalla precisione necessaria alla nostra applicazione.

Il limite di questo metodo è che si applica solo a reti neurali con due strati: quello degli input e quello degli output.

La rinascita dell'interesse per il connessionismo (così viene chiamata la teoria che cerca di imitare i sistemi nervosi biologici connettendo tra di loro tante unità funzionali, ognuna delle quali esegue un semplice calcolo) avvenne principalmente per la scoperta della regola di retropropagazione (o propagazione inversa, in inglese back-propagation), che permette di applicare la regola delta a reti neurali multi-strato. Sebbene sia stata indipendentemente scoperta più volte essa viene in genere accreditata a David E. Rumelhart e collaboratori, fondatori del gruppo di ricerca PDP (Parallel Distributed Processing).

Una rete multi-strato è di questo tipo:

Nel caso in figura abbiamo 4 neuroni di input, 2 di output e 3 nello strato intermedio o nascosto.

La retropropagazione permette di applicare la regola delta partendo dai due strati più a destra, e propagando all'indietro il calcolo della variazione dei pesi sinaptici. Si può avere un numero qualsiasi di strati nascosti.

Il metodo di retropropagazione è ancora oggi uno dei più utilizzati ed efficaci. Una rete neurale multi-strato è infatti in grado di "apprendere" tutte le funzioni praticamente utilizzate.

Più precisamente, attraverso risultati di K. Hornik (1991) e altri, si dimostra che una rete neurale con retropropagazione con tre strati (uno nascosto) è in grado di approssimare quanto si vuole qualsiasi funzione a valori reali definita su un ipercubo reale n-dimensionale. In particolare può apprendere qualsiasi funzione booleana in n variabili!

Quasi contemporaneamente alla retropropagazione il fisico J.J. Hopfield in una serie di articoli dal 1982 al 1985 (l'ultimo in collaborazione con D.W. Tank) presentò un modello di reti neurali ad alta connessione che porta ora il suo nome e che rappresentò un'altra forte motivazione per la ripresa delle ricerche nell'area del connessionismo.

La rete di Hopfield non è stratificata ed ogni neurone è trattato allo stesso modo: non esistono neuroni di input o di output privilegiati.

Vi sono N neuroni, indicizzati dagli interi 1..N. Il neurone i è connesso al neurone j con un peso sinaptico W(i,j), dove si richiede W(i,i)=0 e W(i,j)=W(j,i).

Il tempo è considerato discreto: t=0,1,2…

In ogni istante t il neurone i possiede un potenziale X(t,i) che può valere 1 o -1.

Una data distribuzione di potenziali è detta uno stato del sistema.

All'istante t+1 il neurone i assume un potenziale che dipende dalla somma pesata dei potenziali di tutti gli altri neuroni:

dove F è la funzione segno sopra definita.

Fissati i W(i,j) ed uno stato iniziale X(0,i) (i,j = 1..N) il sistema si evolve in modo deterministico nel tempo t=1,2.., passando da uno stato all'altro; si tratta quindi di un sistema dinamico discreto molto particolare.

Hopfiled provò che un sistema di questo genere giunge in un numero finito di passi ad un punto fisso: non può entrare in un ciclo infinito.

Vi è ovviamente un numero finito di punti fissi. Ogni punto fisso P possiede un bacino di attrazione (l'insieme degli stati a partire dai quali il sistema arriva a P) più o meno grande.

Hopfield dimostrò che questi punti fissi corrispondono ai minimi della funzione di energia H da lui introdotta:

L'idea è quella di modellare la superficie di energia in modo tale che i suoi minimi corrispondano agli stati che la macchina deve apprendere.

Per visualizzare la cosa supponiamo che i neuroni siano disposti in una griglia rettangolare nel piano e che -1 significhi bianco ed 1 nero. Allora uno stato corrisponde ad una figura. Se sottoponiamo alla macchina come stato iniziale una certa configurazione essa si evolverà verso una delle figure fisse (stati finali). Se per esempio i minimi corrispondono alle lettere dell'alfabeto, sottoponendo al sistema una lettera A distorta, la macchina arriverà allo stato corrispondente alla A dell'alfabeto, purché la prima A non sia troppo dissimile, ossia appartenga al giusto bacino di attrazione.

La fase di apprendimento consiste dunque nel fissare i W(i,j), e viene eseguita in colpo solo.

Se vi sono m configurazioni M(z,i) (z=1..m, i=1..N) da memorizzare, è sufficiente, come ha dimostrato Hopfield, porre:

per far sì che ad esse corrispondano minimi di E, cioè punti fissi.

Naturalmente vi sono dei limiti alla capacità di memorizzazione della rete. Se i pattern sono generati casualmente in modo indipendente la rete può immagazzinare fino a 0.15N immagini, con una probabilità di recuperare l'informazione giusta maggiore del 99%.

Non è poco! Supponiamo che ogni neurone sia collegato con un pixel dello schermo del computer con risoluzione 640x400 (in questo caso N = 256000); possono essere memorizzate fino a 38400 immagini in bianco e nero formato 640x400: un bel numero!

Una domanda: dove sono le immagini? Non vi è un luogo specifico ove si trovi una singola immagine; esse sono contenute tutte insieme nella distribuzione dei pesi sinaptici: un dato input farà affiorare un certo "ricordo" piuttosto che un altro. Vediamo qui un chiaro esempio di memoria associativa o CAM (Content Addressed Memory): essa si contrappone a quella dei nostri computer in quanto è indirizzata non a certe posizioni in memoria ma ai contenuti.

I vantaggi sono importanti. Il degrado di molti neuroni o pesi sinaptici non altera significativamente le capacità di riconoscimento della rete di Hopfield, mentre l'errore in un solo bit nell'indirizzo di memoria di una immagine ne rende impossibile il recupero negli ordinari calcolatori.

Inoltre, proprio come accade negli esseri viventi la rete può riconoscere immagini alterate o recuperare l'intera immagine da un suo particolare.

Esistono alcuni problemi. In primo luogo più le immagini sono correlate minore è la capacità di memorizzazione. In secondo luogo la macchina memorizza anche stati spuri, che non le sono stati presentati nella fase iniziale di apprendimento. Per esempio lo stato "opposto" (dove 1 si scambia con -1) corrisponde sempre ad un minimo di E, cioè ad un punto fisso (come immagine è esattamente il "negativo" fotografico). Ma vi possono essere stati spuri (cioè minimi locali) del tutto imprevedibili. In fondo la macchina esibisce una certa creatività, come se - nell'esempio dell'alfabeto - introducesse altri segni.

Possiamo immaginare il processo di recupero dell'informazione come la caduta di una pallina.

La superficie dell'energia è cosparsa di buche (i minimi prodotti nell'apprendimento) più o meno profonde (a seconda dell'energia dello stato corrispondente) e circondate da un avvallamento più o meno ampio (il bacino di attrazione). L'input (cioè lo stato inziale, l'immagine sottoposta alla macchina) corrisponde ad una certa posizione sulla superficie: supponiamo di porre in quel punto la pallina; data la dinamica del sistema essa cadrà inevitabilmente in una ben determinata buca e vi rimarrà. Nel fondo della buca vi è lo stato corrispondente al "ricordo" associato all'immagine, che costituisce poi l'output.

Gli stati spuri hanno livelli di energia più alti (la buca è meno profonda) e bacini di attrazione più stretti. Basterebbe "scuotere" un poco la superficie per far uscire la pallina dalla buca sbagliata e farla cadere nella più vicina ampia ed profonda buca - quella giusta - dalla quale invece non uscirà così facilmente.

Come è possibile "agitare" la superficie? Viene in aiuto una profonda ed interessante connessione tra le reti neurali di Hopfield ed il magnetismo.

Esiste un isomorfismo tra il modello di Hopfield ed il modello di Ising del magntismo (a temperatura zero). Il modello di Ising descrive un sistema formato da atomi dotati di spin il quale può assumere due versi: su e giù (1, -1). Tutti questi minuscoli magneti interagiscono l'uno con l'altro. Alcuni di essi invertono il loro spin, ed il processo continua fino al raggiungimento dell'equilibrio, che corrisponde ad un unico stato di bassa energia. La funzione che descrive l'energia nel modello di Ising ha la stessa forma di quella del modello di Hopfield.

I vetri di spin sono particolari leghe (ad esempio rame-manganese) il cui comportamento magnetico è singolare. Un vetro di spin può avere moltissimi stati di bassa energia, difficilmente separabili, proprio come accade sulla superficie di energia di una rete di Hopfield nella quale siano state immagazzinate troppe immagini o troppo simili tra di loro. Il "paesaggio" è quello di una catena di montagne ove vi sono moltissime valli e si vuole trovare le più profonde possedendo solo una visione locale della situazione.

Per cercare uno stato di bassa energia si riscalda il vetro di spin; in questo modo gli orientamenti degli spin si invertono facilmente e c'è una maggiore probabilità di uscire da depressioni poco profonde. Dopo di che lo si rafrredda lentamente e si ripete il processo tante volte quanto basta. Il procedimento viene detto ricottura.

Quando la rete neurale si comporta come un vetro di spin e raggiunge quindi stati finali aleatori indesiderati con troppa frequenza si può usare una tecnica di ricottura simulata.

La temperatura è introdotta mediante una tecnica probabilistica. Vediamo qualche dettaglio. La formula che governa l'evoluzione del sistema diventa ora:

dove a primo membro c'è la probabilità che al tempo t+1 il neurone i-esimo assuma il valore 1 (altrimenti è -1). La funzione F non è più, ovviamente, la funzione segno bensì:

Il parametro T rappresenta la temperatura; si osservi che al tendere di T a zero la funzione F tende alla funzione segno. Se la temperatura tende all'infinito F (z) diventa 1/2 (sono equiprobabili i valori 1 e -1) ed il sistema è caotico. Tanto più alta è la temperatura T tanto più il sistema è "agitato" ed è facile uscire da piccole buche di energia (immagini spurie). La ricottura simulata consiste allora in una successione di riscaldamenti e raffreddamenti, ossia evoluzioni del sistema ad alte temperature che vengono gradualmente diminuite. Questo sistema da ottimi risultati nelle applicazioni.

Una delle caratteristiche principali delle reti neurali è che possono apprendere. Vi sono reti che possono apprendere anche senza insegnante, cioè direttamente dall'osservazione di esempi (non vi è la presentazione di coppie situazione - risposta voluta) come le reti di Kohonen e altre; si rimanda per questo importante sviluppo alla letteratura citata.

Inoltre le reti neurali presentano un decadimento graduale in presenza di lesioni e risultano particolarmente adatte a pilotare macchine che operino in situazioni tali da rendere impossibili riparazioni dirette. Esse sono in grado di rispondere in modo adeguato a configurazioni mai esaminate in fase di addestramento. Possono inoltre recuperare l'intero contenuto dei dati anche in presenza di informazioni parziali.

Le loro applicazioni sono innumerevoli e vanno dalla diagnosi medica, al riconoscimento del parlato (vi sono già computer che eseguono direttamente gli ordini pronunciati dal loro proprietario; questo compito è eseguito da una rete neurale di un migliaio di unità e viene addestrata direttamente dall'utente), alla lettura ad alta voce (voce sintetizzata) di testi, alla guida automatica di veicoli.

Vengono utilizzate nelle scienze finanziarie, in psicologia, neurologia e informatica.

Le ricerche in questo campo sono rese ancora più interessanti dal fatto che in esse confluiscono conoscenze provenienti dalla fisica, dalla biologia, dalla teoria dell'informazione e dalla matematica.

.

Gli automi cellulari vennero introdotti agli inizi degli anni '40 da due grandi matematici: John von Neumann e Stanislav Ulam.

Le caratteristiche principali di un automa cellulare sono le seguenti:

1. E' un sistema discreto nello spazio e nel tempo:

Inoltre ogni cella può assumere uno stato scelto in un insieme finito di stati possibili.

2) E' locale:

Lo stato di ogni cella C in dato istante è determinato esclusivamente dagli stati assunti,

nell'istante precedente, dalle celle appartenenti all'intorno di C.

3. E' omogeneo:

La struttura dell'intorno è uguale per ogni cella, così come per ogni cella la legge di evoluzione è la medesima.

4. E' parallelo:

Ad ogni istante tutte le celle sono aggiornate simultaneamente.

L'evoluzione - completamente locale - di queste macchine porta a volte a comportamenti globali, dati dalle configurazioni risultanti dall'insieme di tutte le celle, complessi e imprevedibilmente ricchi. Molte unità semplici danno luogo ad una super-unità complessa.

La filosofia sottostante all'idea di automa cellulare può essere vista come una critica della ragion centrale. Non vi sono intelligenza, volontà o coscienza che controllino il sistema; esse sono distribuite nel sistema stesso. Si osserva l'emergere di un in-dividuo che in realtà è assolutamente frammentato; si modella l'apparizione di un nuovo livello ontologico.

Von Neumann e i suoi collaboratori erano interessati alla possibilità di creare un costruttore universale (una macchina capace di fabbricare altre macchine, ricevutone il progetto), un auto-replicatore (una macchina in grado di fabbricare una copia di se stessa che possieda a sua volta la medesima capacità), un calcolatore universale (una macchina in grado di eseguire qualsiasi algoritmo finito, come la macchina di Turing universale).

Von Neumann voleva inizialmente costruire fisicamente macchine di questo tipo, ma Ulam lo convinse ad esplorare a questo fine le possibilità degli automi cellulari, e a cercare configurazioni in grado, per esempio, di autoriproduzione. Venne ideato un automa bidimensionale con 5 celle d'intorno e ventinove stati che risolveva il problema. Questo automa non si poteva realizzare materialmente perché necessitava di un numero troppo elevato di celle per poterlo simulare ma in ogni modo esisteva.

Vediamo ora due esempi affascinanti, che comprendono la costruzione di un calcolatore universale in un automa cellulare con appena due stati: gli automi lineari di Wolfram ed il gioco della vita di Conway.

Stephen Wolfram, un fisico ideatore tra l'altro del famoso programma di calcolo simbolico Mathematica, si occupò negli anni '80 della meccanica statistica degli automi cellulari lineari.

Un automa cellulare lineare si può vedere come una stringa di celle estesa all'infinito in entrambe le direzioni (in ogni istante solo un numero finito di esse è attivo):

Wolfram iniziò con lo studio delle regole binarie di raggio 1.

L'intorno di ogni cella è dato dunque dalla cella stessa, da quella alla sua sinistra e da quella alla sua destra; gli stati sono 0 ed 1 (rappresentati da due colori, per esempio bianco e nero).

Gli stati hanno quindi 8 possibili configurazioni: (0,0,0), (0,0,1), (0,1,0),…,(1,1,1); una regola deve assegnare ad ognuna di esse 0 od 1, e può essere vista come una stringa di 8 bit.

Per esempio la regola data dalla tabella:

si può identificare con il numero binario 01011010, corrispondente al numero decimale 90, e per questo viene chiamata regola 90. Supponiamo di annerire la casella se il suo stato è 1 e di lasciarla bianca altrimenti. In un certo istante l'automa apparirà come una stringa di caselle bianche o nere; mettendo le stringhe una sotto l'altra si ha una rappresentazione visiva dell'evoluzione.

Nella figura seguente si vede un'evoluzione molto più lunga della legge 90:

La legge 90 è spesso citata anche perché ha una descrizione in termini di logica: il bit assunto da una cella è semplicemente lo XOR dei due bit sopra di lei, quello a sinistra e quello a destra (non dipende dal proprio stato precedente).

Lo stato iniziale scelto nei due esempi di legge 90 è formato da una singola cella attivata.

Ecco quello che accade con uno stato iniziale casuale:

Nella sua ricerca del 1984 Wolfram individuò quattro classi di comportamento degli automi cellulari:

Dopo un numero finito di passi l'automa perviene ad uno stato stabile, a partire da (quasi) qualsiasi stato iniziale.

L'automa entra in un ciclo (di periodo non grande). Questi automi sono una sorta di filtro, e possono essere usati per il trattamento delle immagini.

L'automa produce configurazioni aperiodiche. Di solito sono immagini auto-similari (frattali). La legge 90 appartiene a questa classe.

L'automa è assai sensibile alle condizioni iniziali. Anche se gran parte degli stati iniziali portano alla quiescenza, alcuni di essi conducono a configurazioni complesse e persistenti. In questa classe si trovano gli automi capaci di computazione universali; qui si trova il gioco Life di cui parleremo tra poco.

Vediamo alcuni esempi tratti dalle regole binarie di raggio 1 con la numerazione di Wolfram.

La regola 4 appartiene alla classe 1. Dopo un passo rimangono attivi solo i bit 1:

La regola 54 appartiene al confine tra le classi 2 e 3. Prima di arrivare allo stato periodico presenta lunghi transienti caotici:

La regola 30 è nella classe 3. Presenta un alto grado di casualità spaziale e temporale; per questo viene studiata per applicazioni crittografiche:

Infine la regola 110 è l'unica accreditata tra le 256 lineari di raggio 1 ad appartenere alla classe 4:

Aumentando il raggio ed il numero degli stati, il numero delle regole cresce esponenzialmente. Mentre la percentuale delle regole caotiche tende a diventare il 100%, le poche regole di classe 4 (sempre più difficili da "pescare") diventano più interessanti e ricche di sorprese.

John H. Conway scoperse Life - il gioco della vita - nel 1970. Life è un automa cellulare bidimensionale dove ogni cella ha un intorno formato dalle 8 celle vicine.

Se la cella è inattiva e nell'intorno vi sono esattamente 3 celle attive, la cella si attiva: regola di nascita.

Se la cella è attiva e nell'intorno vi sono 2 o 3 celle attive la cella rimane attiva, altrimenti entra in stato quiescente all'istante successivo: regola di sopravvivenza.

Life appartiene alla classe 4 di Wolfram, e le configurazioni che sono via via scoperte costituiscono una continua sorgente di stupore.

Presentiamo alcuni personaggi fondamentali del gioco. Il glider (aliante):

L'aliante è formato dalle 5 celle nere; la sua evoluzione è mostrata nella figura: al quinto passo si ripete lo stato iniziale, però l'aliante si trova spostato di una casella in basso e a destra. Viste le regole la velocità massima di spostamento di un oggetto di Life è 1 casella per passo (ciclo di aggiornamento o istante del nostro tempo discreto); dunque l'aliante viaggia ad un quarto della velocità della luce (nel gergo di Life si dice velocità della luce la massima velocità consentita dal gioco).

Un aliante attraversa scivolando dolcemente lo schermo del computer ove avviene la simulazione per sparire oltre i suoi bordi e seguitare per sempre il suo cammino nell'infinito reticolo di Life.

Ovviamente il suo cammino proseguirà se non incontra altri esseri che possano modificarlo o distruggerlo. Per esempio lo eater (divoratore):

Il divoratore semplicemente allarga le fauci ed inghiotte l'aliante (purché arrivi in una certa direzione).

Qual è la massima parte di spazio che una configurazione può arrivare ad occupare durante la sua evoluzione (facendo tendere il tempo all'infinito)? Si congettura che sia 1/2.

Un personaggio che attua questo compito addirittura ad 1/2 della velocità della luce nelle quattro direzioni è il piccolo Max:

Ecco come si evolve:

Viene tirato nella quattro direzioni dai quattro individui ai suoi vertici che si spostano di una casella ogni due cicli.

Importantissimo è il glider gun (cannone di alianti):

Evolvendosi genera una successione infinita di alianti che si muovono nella stessa direzione (in questo caso sud-est):

E' molto interessante il problema della sintesi in Life. Forse un intero universo può essere condensato in una piccola zona dello spazio che evolvendosi si espanda e crei nuovi mondi.

Per esempio i dodici alianti qui sotto:

negli istanti successivi collidono e la loro collisione genera un cannone di alianti che inizia infaticabile a sparare infiniti alianti!

Esistono comunque mondi che non possono essere sintetizzati, per il semplice fatto che non derivano da nessuna configurazione precedente: da essi si può solo partire ma non ci si può arrivare! Per questo vengono chiamati Giardini dell'Eden. La loro reale esistenza è rimasta una congettura per parecchio tempo, poi è stata dimostrata con un difficile teorema; recentemente attraverso ricerche su computer sono stati trovati Giardini dell'Eden composti di poche centinaia di celle.

Rimane aperto il problema: il figlio di un Giardino dell'Eden (la configurazione seguente) può avere un nonno (si rifletta bene prima negarne la possibilità…)?

In realtà Life è molto più di uno svago. Pensiamo ad un aliante come ad un bit; un cannone di alianti è dunque una successione di bit. Questa successione può essere modulata utilizzando altri cannoni, perché due alianti che si incontrano con un certo angolo si elidono. Usando gli alianti, i cannoni e i divoratori si possono costruire in Life unità logiche AND, OR, NOT, nonché banchi di memoria che permettono il trasferimento di dati. E' insomma possibile costruire dentro Life un computer.

Utilizzando queste idee Conway ha provato che in Life esistono una macchina di Turing universale, un costruttore universale, un autoreplicatore. Il progetto di von Neumann si realizza in Life, un semplice automa cellulare bidimensionale a due stati!

Life presenta aspetti inquietanti, proprio per la sua semplicità e trasparenza di definizione. Per esempio l'esistenza di una macchina di Turing universale ci pone di fronte a questioni di indecidibilità. Si dice indecidibile una domanda che, per come è posta, ammette risposta sì o no, ma è tale che nessun algoritmo finito può pervenire a questa risposta. Il problema dell'arresto di una macchina di Turing è indecidibile. In parole povere non esiste un programma che possa decidere se un qualsiasi programma sottoposto al suo esame terminerà il suo compito o "girerà" senza fine sul computer. Si ottiene come conseguenza che nessuna macchina può decidere se una data configurazione di Life arriverà ad estinguersi o meno!

Questa prospettiva affascinò C. Langton, fondatore dell'Istituto di Vita Artificiale presso l'Istituto di Santa Fe, il quale recentemente ha dichiarato:

"E' nostra convinzione che sia possibile inserire nei computer universi sufficientemente complessi da dar luogo a processi che, rispetto a tali universi, possono essere considerati processi viventi. Ma non sarebbero costituiti della stessa materia… Ciò fa balenare l'inquietante possibilità che stiamo creando i prossimi esseri viventi dell'universo."

Non è facile esplorare queste possibilità di vita. Nel caso di Life abbiamo una regola a 2 stati con un intorno di 9 celle (inclusa la cella centrale, che influenza lo stato successivo). Vi sono 2 elevato a 512 regole di questo tipo!

E' stata introdotta una notazione standard per le regole tipo Life nel formato A/B (regola di sopravvivenza/regola di nascita) dove A è una stringa di cifre le quali rappresentano i numeri di celle attive nell'intorno della cella attiva che permettono la sopravvivenza, B è una stringa di cifre le quali rappresentano i numeri di celle attive nell'intorno della cella quiescente che danno luogo alla nascita. Per Life la notazione è 23/3.

La regola /234 indica che nessuna cella attiva sopravvive alla generazione seguente (il primo campo A è vuoto) mentre una cellula inattiva si accende al passo successivo se ci sono 2,3 o 4 celle attive intorno a lei. Questa regola produce configurazioni simili a merletti, di cui diamo un piccolo e particolarissimo esempio:

La regola 12345/3 è identica a Life per la regola di nascita, ma consente la sopravvivenza della cellula attiva in una gamma di casi più ampia: 1,2,3,4 o 5 celle attive. Genera configurazioni labirintiche; un esempio:

Langton ebbe un'ispirazione per orientarsi in questi oceani di regole (oceani infiniti per l'uomo, almeno sul piano computazionale): il parametro lambda.

Dato un automa cellulare controllato da una regola R con un numero N di possibili configurazioni di intorno (8 nel caso degli automi lineari di Wolfram con raggio 1, 512 nel caso di automi tipo Life, etc…) l è la probabilità che, in base ad R, una delle N configurazioni porti ad una cella attiva, ovvero è la probabilità di una transizione non-quiescente.

Langton faticò non poco per affermare la validità scientifica delle ricerche sulla vita artificiale, peregrinando da un istituto all'altro; quando mostrava i suoi programmi la risposta usuale era "interessante, ma è solo un videogame!". Narra nel suo diario che una sera, completamente solo in un laboratorio pieno di computer, osservando le creature che si agitavano sullo schermo percepì una presenza nella stanza. Ma non c'era nessuno tranne lui. Comprese allora intimamente che la vita si manifestava nella macchina che aveva di fronte! Scoperse che la complessità arrivava ad un livello creativo quando l era intorno a 0.3; si arriva altrimenti ad evoluzioni periodiche o caotiche (per Life il valore di l è circa 0.27).

Langton coniò il termine edges of chaos (margini del caos) per indicare la zona ai confini tra gli stati "ordinati" (stabili o periodici) e quelli caotici, nella quale si trova la complessità, che si evidenzia in particolare con la capacità ci computazione universale.

In questo cosmo informatico, nella stretta e frastagliata zona di confine dei margini del caos, esistono altre vite al di fuori di Life? Nessuno le ha trovate. Del resto poiché Life è capace di computazione universale ogni vita "algoritmica" è in linea di principio riproducibile in esso. Dunque in una scacchiera infinita, inizializzata a caso, potrebbero manifestarsi (se esistono) queste vite sconosciute ed avvenire veri e propri incontri ravvicinati con gli alieni!

Gli automi cellulari sono oggi assai utilizzati anche da fisici e chimici per simulare (tra l'altro) la dinamica di sistemi di particelle (reticoli di gas), il modello di Ising o le reazioni diffusive.

Probabilmente siamo solo agli albori di una descrizione matematica della natura completamente nuova, che si presenta come alternativa a quella classica, consolidata da circa 300 anni, basata sulle equazioni differenziali.

Questa rivoluzione è indotta dall'uso dei computer. Partendo da un'equazione differenziale che descrive il sistema, per ottenere un modello si è forzati a rendere discreti spazio e tempo; le variabili reali - che esprimono la continuità - devono diventare dati a precisione finita - cioè discrete - per entrare nella memoria della macchina.

Come scriveva il fisico Tommaso Toffoli (uno dei promotori dell'uso degli automi cellulari, con Norman Margolus e altri) nell'84:

"..nel modellare la fisica con l'approccio tradizionale, noi utilizziamo - per ragioni storiche - un apparato matematico che contiene probabilmente molto più di quanto abbiamo bisogno, e dobbiamo faticare non poco per escludere queste "caratteristiche avanzate" in modo tale da poter concludere il nostro lavoro malgrado esse.."

Nella visione classica esistono leggi - espresse da eleganti formule differenziali - cui si adegua la natura. Nell'approccio bottom-up, che gli automi cellulari condividono con le reti neurali, le leggi e la complessità emergono dall'interazione locale di tante unità identiche. Non vi è un centro privilegiato, bensì il centro è in ogni luogo.

Si potrebbe concludere, con Meister Eckhart, Deus est totus in quodlibet sui.