venerdì 27 luglio 2018

I Rompicapi di Alice: La formica di Langton

Era il 1986 quando Christopher Langton propose di utilizzare una formica per studiare la biochimica della vita(1). La formica di Langton, però, non era una vera e propria formica, ma un automa cellulare. Prima di vedere come funziona la proposta di Langton, vale la pena introdurre gli automi cellulari e, tra questi, ilpiù famoso di tutti, il gioco della vita di Conway.
Auto-replicazione
Tutto ebbe inizio a Los Alamos con John von Neumann e Stanislaw Ulam. I due stavano studiando, rispettivamente, i sistemi autoreplicanti il primo e la crescita dei cristalli il secondo.
Il progetto iniziale di von Neumann si basava sull'idea di un robot in grado di costruire un altro robot: sviluppando questo progetto, il matematico si rese conto dei problemi insiti in esso, come il costo eccessivo nel fornire al robot le molte parti necessarie per costruire un altro robot a lui identico.
L'idea di Ulam di utilizzare un modello discreto per l'autoreplicazione in qualche modo venne ripresa dai due matematici quando, sul finire degli anni Cinquanta, crearono un modello per calcolare il movimento di un liquido. Essi consideravano il liquido come un gruppo di unità discrete e calcolavano il moto di ciascuna unità in base al comportamento dei vicini: nasceva il primo sistema di automi cellulari.
I due realizzarono un sistema in grado di copiare e costruire dalle celle di partenza in funzione di alcune regole base sulla vicinanza(2). Tale sistema sarebbe stato in grado di realizzare un numero infinito di copie di se stesso all’interno dell’universo cellulare dato: questo è il così detto costruttore universale di von Neumann.
Il gioco della vita

Il gioco della vita di Conway - Conway's game of life - #MateInItaly

Un post condiviso da Gianluigi (@ulaulaman) in data:

Facciamo un salto fino agli anni Settanta quando John Conway inventa un nuovo automa cellulare, il Gioco della Vita (Game of Life), diffuso per la prima volta da Martin Gardner sulle pagine della sua ribrica di giochi matematici per Scientific American(3).
Su una plancia di celle quadrate bianche grande a piacere si pongono alcune di esse nere: questa configurazione iniziale è detta generazione 0.
Da qui in poi si osserva lo sviluppo delle generazioni successive, che si evolveranno in base a queste semplici regole:
  1. se una cella nera ha due o tre vicini, allora sopravvive fino alla generazione successiva; il destino dei vicini dipende dai loro vicini;
  2. se una cella nera ha quattro o più vicini, allora alla generazione successiva muore, ovvero la cella diventa bianca;
  3. se una cella nera ha uno o nessun vicino, allora alla generazione successiva muore;
  4. se una cella vuota ha esattamente tre vicini, allora alla generazione successiva avviene una nascita, ovvero la cella vuota diventa nera.
Il gioco così creato è di tipo deterministico, ma partendo da configurazioni differenti, anche di poco (differenze di appena una cella) è possibile ottenere risultati differenti e imprevedibili: proprio come la teoria del caos, ma a un livello più semplice, il Gioco della Vita permette di evidenziare come l’imprevedibilità e la complessità possano emergere da basi deterministiche.
Ad ogni buon conto, evolvendo differenti sistemi di Vita, le configurazioni, su tempi lunghi, possono(4):
  1. scomparire completamente;
  2. raggiungere uno stato stazionario;
  3. ripetere la stessa sequenza per sempre;
  4. ripetere la stessa sequenza per sempre, ma in una posizione ogni volta differente;
  5. comportarsi in maniera caotica;
  6. esibire un comportamento computazionale, ovvero comportarsi come una macchina di Turing.
In particolare dall'ultimo punto emerge una curiosità particolare: è possibile, cioè, utilizzare il Gioco della Vita per eseguire dei calcoli, proprio come dovrebbe fare una macchina di Turing, ma a una velocità estremamente bassa rispetto agli algoritmi dedicati allo scopo e quindi con ben scarsa utilità.
Inoltre, esplorando il Gioco in lungo e in largo, sono state scoperte una gran varietà di forme periodiche che spesso emergono nell'evoluzione delle configurazioni. Alcune vengono chiamate astronavi (spaceship) che si muovono orizzontalmente all'interno della plancia. Alcune emettono scintille durante il movimento, altre hanno una scorta.
Tra le più famose, invece, c'è l'aliante (glider), scoperta da Richard Kenneth Guy nel 1970, che si muove diagonalmente lungo le celle con un periodo di quattro generazioni, durante le quali cambia forma e posizione. L'aliante emerge spesso nell'evoluzione delle configurazioni e si muove a una velocità di $c/4$, dove $c$, detta velocità della luce, coincide con lo spostamento di una cella in una generazione.
Una formica a zonzo
Con l'obiettivo di simulare e studiare la logica molecolare dei sistemi cellulari biologici, Langton propose un particolare automa cellulare(1): una formica che si muove su una plancia di celle bianche e nere. Può muoversi verso nord, sud, est, ovest. Ogni volta che si sposta, ovvero ad ogni avanzamento del tempo, i suoi movimenti vengono dettati da queste semplici regole(4):
  1. se finisce su una cella nera, ruota di 90° a sinistra;
  2. se finisce su una cella bianca, ruota di 90° a destra;
  3. la cella che ha appena abbandonato cambia colore (da bianca a nera o viceversa).
La plancia di partenza può essere chiazzata a piacere o monocromatica (completamente bianca o nera). Evolvendo il sistema, la figura che la formica realizza sulla plancia si fa via via sempre più complicata, in linea perfetta con quanto emerso nel Gioco della Vita, a cui si ispira.
Il comportamento della formica di Langton segue abbastanza bene lo schema seguente(5):
  1. durante il primo centinaio di mosse, la formica crea delle forme abbastanza semplici con un certo grado di simmetria;
  2. durante un numero di mosse dell’ordine delle 10000, la formica genera un percorso caotico e imprevedibile;
  3. alla fine ripete in maniera indefinita la stessa sequenza di 104 mosse che si sposta in diagonale, costruendo la così detta autostrada.
Il fatto sorprendente nelle autostrade è che queste emergono alla fine quale che sia la configurazione di partenza! Il problema è dimostrare che la formica costruirà sempre un'autostrada o se esistono configurazioni iniziali particolari che impediscono tale conclusione(4).
Inoltre il gioco risulta equivalente a un calcolatore universale (una macchina di Turing), con conseguente esistenza di problemi indecidibili(6): quindi, forse, il fatto che le autostrade sono l'esito inevitabile di qualunque conclusione è proprio uno di questi problemi indecidibili.
La vita e l'universo non sono automi cellulari
Per chiunque conosca anche un po' le posizioni filosofiche di Alan Moore, l'autostrada costruita dalla formica di Langoton alla fine di un percorso caotico fa indubbiamente pensare alla soluzione del fumettista per conciliare insieme determinismo e libero arbitrio: immaginare la vita come un percorso non determinato che si svolge all'interno di un tubo. Questo limita le scelte, ma esse restano sufficientemente ampie da lasciare la sensazione a chi le compie di avere, in qualche modo, un libero controllo sulle stesse. In effetti, se si prova a realizzare una formica di Langton in tre dimensioni(7), l'autostrada tridimensionale che ne emerge ricorda molto da vicino l'idea di Moore.
Il punto è che gli automi cellulari possono essere un aiuto per la simulazione e la comprensione di alcuni dei comportamenti reali, ma né gli esseri viventi, né l'universo stesso possono essere considerati degli automi cellulari. A suggerirlo è proprio Conway, il cui risultato più interessante, il Teorema del libero arbitrio, ho recentemente esaminato. In un'intervista concessa a Notices of American Mathematical Society, Conway afferma(8):
Penso che [Steven Wolfram] sia in errore. E sono piuttosto stupito che egli abbia l'opinione che ha, poiché si suppone abbia studiato fisica. Non dovrei dire "si suppone" - scusami. Dovrebbe essere consapevole del fatto che l'universo si comporta in una maniera che - almeno come credono molti fisici competenti - è non deterministica. E gli automi cellulari sono cose che, come il gioco della vita, sono deterministiche. Così nella mia opinione, è dimostrabile che l'universo non è un automa cellulare.
E questo, in un certo senso, mette al loro posto gli automi cellulari: dei giochi interessanti per matematici curiosi!
Consigli per lettori di fantascienza
Gli automi cellulari e i robot autoreplicanti sono stati protagonisti di racconti e romanzi di fantascienza, per cui mi sembra giusto concludere con alcuni consigli di lettura. In particolare inizierei con Microgenesi di Wil McCarthy: ambientato nel 2106, vede gli umani lottare per la sopravvivenza contro delle nanomacchine autoreplicantesi che stanno invadendo il Sistema Solare minacciando così l'esistenza della vita così come la conosciamo. Il protagonista, John Strasheim, a un certo punto si trastulla con il Gioco della Vita, che diventa un modo per comprendere, anche se in maniera approssimata, il comportamento di queste nanomacchine. La lettura di questo bel romanzo è stata anche il mio primo approccio al gioco ideato da Conway, per cui vi consiglio di recuperarlo in qualche modo (girando per le bancarelle o sperando di trovare un'edizione digitale).
Altro bel romanzo sull'autoreplicazione è Il sistema riproduttivo di John Sladek, un capolavoro dell'umorismo che, dimenticandosi dei problemi di risorse rilevati da von Neumann nella progettazione di robot di tal genere, realizza un'esilarante invasione delle macchine.
Meno esilarante è, invece, Uomini e androidi di Edmund Cooper, di cui ho recentemente scritto e su cui non spendo altre parole in più. Entrambi questi romanzi li ho già io stesso recuperati sulle bancarelle, ma secondo me può valere la pena cercare l'edizione digitale: non escludo che Mondadori abbia digitalizzato tutto il catalogo Urania.
  1. Christopher G Langton, 1986, ‘Studying artificial life with cellular automata’, Physica D: Nonlinear Phenomena, vol. 22, no. 1-3, pp. 120-149 doi:10.1016/0167-2789(86)90237-X90237-X)↩
  2. J. Von Neumann, Theory of Self-Reproducing Automata, Arthur W. Burks, ed. (Univ. of IUinois Press, Urbana, IL, 1966)↩
  3. Gardner, M. (1970). Mathematical games: The fantastic combinations of John Conway’s new solitaire game “life”. Scientific American, 223(4), 120-123. (pdf | html)↩
  4. Stewart, I. (2010) La piccola bottega delle curiosità matematiche del professor Stewart, Codice Edizioni, edizione speciale per il mensile Le Scienze.
    Leggi anche:
    Stewart, I. (1994). The ultimate in anty-particles. Scientific American, 271(1), 104-107. (pdf)↩
  5. Gale, D., Propp, J., Sutherland, S., & Troubetzkoy, S. (1998). Further Travels with My Ant. In Tracking the Automatic ANT (pp. 137-149). Springer, New York, NY. (arXiv)↩
  6. Gajardo, A.; Moreira, A.; Goles, E. (15 March 2002). "Complexity of Langton's ant". Discrete Applied Mathematics. 117 (1-3): 41–50. doi:10.1016/S0166-218X(00)00334-6. (pdf)↩
  7. Hamann, H. (2003). Definition and behavior of Langton's ant in three dimensions. COMPLEX SYSTEMS-CHAMPAIGN-, 14(3), 263-268. (pdf)↩
  8. Dierk Schleicher (2013). Interview with John Horton Conway. Notices of American Mathematica Society, vol. 60, n. 5, pp.567-575 (pdf)↩
at

Nessun commento:

Posta un commento