venerdì, maggio 01, 2009

La III Classe di Wolfram: caos dagli Automi Cellulari.


Il caos deterministico "classico" ha alcune caratteristiche fondamentali ben note:
- forte sensibilità alle condizioni iniziali
- divergenza esponenziale delle traiettorie (consegue dalla prima)
- regime dinamico totalmente aperiodico.

Da questo punto di vista, l'evoluzione dinamica di un sistema discreto con spazio di stato finito non può avere l'ultima delle tre caratteristiche: essendo finito lo spazio degli stati, l'evoluzione dinamica si troverà necessariamente a dover ripetere un ciclo di stati ad un certo punto.
Tuttavia è proprio da sistemi appartenenti a questa famiglia che sono venuti risultati tra i più importanti per lo sviluppo della scienza della complessità.
Gli Automi Cellulari sono i veri antesignani dello studio delle dinamiche complesse nei sistemi discreti. Per questa classe di sistemi, non esistendo un criterio universalmente accettato per identificarne il comportamento caotico, si utilizza la classificazione data da Wolfram, che ha diviso gli Automi Cellulari in 4 gruppi secondo il comportamento:
- stato omogeneo (classe I)
- strutture periodiche (classe II)
- caos (classe III)
- casualità pura (classe IV)

E' chiaramenta una classificazione basata sull'osservazione del comportamento di questi sistemi.
Trattandosi di sistemi discreti a spazio finito degli stati, balza agli occhi un'incongruenza: è evidente che dopo un periodo di tempo sufficientemente lungo il sistema dovrà comunque trovarsi ad avere esplorato tutti gli stati possibili, quindi (essendo un sistema deterministico) si troverà a ripercorrere un ciclo. Fino a che punto ha dunque senso parlare di "caos" e "casualità" in sistemi siffatti?

Soprattutto a chi ha avuto esperienza di sistemi dinamici continui, dove esiste sempre la possibilità che le traiettorie possano non auto-intersecarsi mai, questa distonia risalta.

Consideriamo però un semplice automa cellulare costituito da un vettore di N celle, ognuna delle quali può assumere k differenti stati discreti, a seconda degli input che gli provengono dal suo vicinato di n celle. Per ciascuna cella ci saranno k^n possibili configurazioni di input, tante quante sono le disposizioni con ripetizione di k simboli ad n ad n.

La rule table dell'automa cellulare assegna poi alla cella un valore specifico a seconda della configurazione di input: ci sono quindi k^n possibili associazioni tra input ed output per una cella, tante quante sono le possibili configurazioni di input. Chiaramente un AC è ben definito proprio fissando queste k^n associazioni: ma quanti modi ci sarebbero per definire un AC con questi presupposti? Facile: ce ne sarebbero k^(k^n), tanti quante sono le disposizioni con ripetizione di k simboli presi a gruppi di k^n. Questo è il numero degli AC possibili nello spazio definito dai parametri k ed n.

Per N sufficientemente grande, diventa virtualmente impossibile che l'AC possa esplorare tutto lo spazio delle configurazioni in un tempo dato. Ha quindi senso osservare il comportamento dell'AC (in un tempo finito) al limite per N che tende ad infinito nel caso di sistemi di classe III e IV (caos e random).

Wolfram ed altri comparano gli AC di Classe III a sistemi dinamici caotici [...] Dato uno spazio finito di dimensioni "ragionevoli", è quasi certo che gli AC di Classe III non "si ripeteranno" mai, ed anche quando accade essi possono avere cicli estremamente lunghi. Inoltre gli AC di Classe III mostrano sensibilità alle condizioni iniziali: anche la sola modifica di un paio di celle dello stato iniziale può produrre un comportamento radicalmente diverso.[...] Tracciando un paragone tra programmi e AC, i sistemi di Classe III sono molto simili ai generatori di numeri pseudocasuali (PRNG). Dato un "seme" iniziale, un PRNG può produrre sequenze talmente incorrelate che possono facilmente superare la maggior parte dei test usati per identificare i processi casuali (es. rumore bianco).
G.W. Flake - The Computational Beauty of Nature.

Fatte queste osservazioni, la classificazione di Wolfram acquisisce significato perchè permette di inquadrare questi sistemi discreti a stati finiti nell'ambito dei sistemi complessi. Pur non esistendo ad oggi un accordo unanime su cosa sia un comportamento caotico nel caso di sistemi discreti a stati finiti, questo tipo di definizione qualitativa è accettata e sarà usata in questo campo di studi finchè non ne apparirà una migliore.
I sistemi AC di Classe III sono dunque capaci di comportamento caotico - nei termini suddetti - che si manifesta nel tempo (sequenza di stati assunti da una singola cella) e nello spazio (formazione di pattern randomici): il che è già un bel risultato per un sistema in fin dei conti costituito da poche regole semplici.

E la complessità? Quella viene con la IV Classe di Wolfram, la più celebre. Per approfondimenti è disponibile in rete un tesoro di informazioni: The New Kind of Science gratuitamente consultabile.

Ultima riflessione. Se anche lo spazio di stato è finito, esso può essere talmente vasto da consentire una cornucopia di automi cellulari diversi, ognuno con una gran quantità di stati possibili. Se ipotizzassimo che la rule table di un automa cellulare possa mutare nel tempo per adattamento a condizioni ambientali, troveremmo che pur con vincoli così stringenti su k ed n lo spazio delle possibilità avrebbe una vastità davvero enorme: un numero minore di particelle ha generato un universo di diversità, quale quello in cui noi viviamo, avendo a disposizione probabilmente meno di 5 interazioni possibili con altre particelle.

6 commenti:

aubreymcfato ha detto...

Bel post, semplice e chiaro. Io adesso continuo a sfogliarmi l'archivio, tu però pensa al prossimo che io un post così lo aspettavo da mo' ;-). Complimenti

Stefano ha detto...

Grazie, troppo buono!

lealidellafarfalla ha detto...

Bello...è il motivo per cui ancora nessuno è riuscito a ripetere un Grande Slam ;-)

Anonimo ha detto...
Questo commento è stato eliminato da un amministratore del blog.
オテモヤン ha detto...
Questo commento è stato eliminato da un amministratore del blog.
Anonimo ha detto...
Questo commento è stato eliminato da un amministratore del blog.