giovedì 12 maggio 2016

Il gioco della vita!

Cari lettori del Tamburo, oggi parliamo del gioco della vita.
No, non effettueremo un sondaggio su quale sia stato il gioco preferito della vostra vita, bensì analizzeremo brevemente un gioco che ha molto a che spartire con la matematica e la biologia.
Trattasi appunto del Gioco della vita, in inglese Game of Life, il quale altro non è che un automa cellulare.
Che diavolo significa?
Quando un bambino delle elementari effettua una moltiplicazione con carta e matita, egli deve innanzitutto osservare i numeri da moltiplicare, tenerli (almeno parzialmente) a mente, per poi arrivare alla soluzione scritta sulla carta.
In sostanza, egli osserva, tiene a mente e agisce!
Il meccanismo di calcolo più basilare concepito dai matematici viene chiamato automa a stati finiti ed esso procede sulla base del medesimo principio: osservare, tenere a mente e agire.
L'automa osserva gli altri automi intorno a lui (immaginando che degli automi identici siano disposti su tutte le caselle di una scacchiera infinita), dopodiché tiene a mente lo stato nel quale esso si trova (questi stati interni risultano finiti, da qui la denominazione fornita prima) e agisce modificando il suo stato secondo le convenzione fissate che lo caratterizzano.
Un calcolatore elementare che funziona nella suddetta maniera viene detto anche automa cellulare.
Un banale esempio è dato dall'automa Spostamento a Est: ogni cellula possiede due stati possibili, 0 e 1 (rappresentabili per mezzo della contrapposizione vuoto o pieno, oppure bianco o nero).
Per cambiare stato, ciascun automa va a valutare lo stato del suo vicino Ovest, lo memorizza e agisce adottandolo come nuovo stato.
Se immaginiamo una figura geometrica composta di 0 e 1 disegnata sul piano e si attiva una singola volta ciascun automa (ossia, in termini tecnici, si calcola una nuova generazione), la figura rappresentata si sposta di una casella in direzione est, come mostrato nell'immagine che segue:

Chi ha ideato il Game of Life?
Il merito si deve a 2 vecchie conoscenze del Tamburo.
Innanzitutto, John von Neumann (protagonista del post "L'alieno e l'angolo solido"), negli anni '40 del XX secolo, ha stabilito l'esistenza di automi autoriproduttori, ovvero che possiedono delle configurazioni le quali, durante il funzionamento, creano delle copie di loro stesse.
In parole povere, il lavoro della geniale mente di von Neumann aveva mostrato che alcuni automi cellulari abbastanza semplici avrebbero dovuto produrre dinamiche evolutive variegate.
Poi, nel 1970, John Horton Conway (l'abbiamo già incontrato nel post "Di gruppi e mostri (matematici)") fissò appunto le regole del Gioco della vita.
Nell'ottobre dello stesso anno, Martin Gardner presentò tale gioco nella rubrica "Giochi matematici" della celebre rivista Scientific American, rendendolo dunque noto al grande pubblico.
Come nel caso dello Spostamento ad Est, il mondo del Gioco della vita è un piano infinito quadrettato in cui ogni casella risulta occupata da una cellula (casella nera, dunque "viva") oppure è vuota (casella bianca, dunque "morta").
Ogni casella possiede 8 caselle adiacenti.
Tra una generazione e la successiva si producono meccanicamente delle nascite e delle morti.
Le semplici regole per l'evoluzione delle celle, data la configurazione di partenza, sono le seguenti:

1) ogni cellula viva con meno di 2 vicini vivi muore (come se la morte fosse causata da sottopopolazione);
2) ogni cellula viva con 2 o 3 vicini vivi sopravvive alla generazione successiva;
3) ogni cellula viva con più di 3 vicini vivi muore (come se la morte fosse causata da sovrappopolazione);
4) ogni cellula morta con esattamente 3 vicini vivi diventa viva nella generazione successiva.

Insomma il Gioco della vita, come l'ha definito lo stesso Conway, altro non è che uno "zero-player-game", giacché esso funziona da solo, senza bisogno dell'intervento di alcun giocatore.
Se le regole presentate appaiono banali, lo stesso non si può affermare relativamente all'evoluzione delle caselle.
Sussistono sicuramente figure che rimangono immobili, come il blocco, l'alveare e la barca, di seguito rappresentate:


Altre presentano invece oscillazioni periodiche, come il cosiddetto "pulsar", che ogni 3 passi di evoluzione torna a essere identico a come era in partenza:

Pulsar

Una domanda lecita a questo punto sarebbe: sono possibili tutti i periodi?
Questione tutt'altro che banale, visto che dopo aver riscontrato, per tentativi, qualche configurazione periodica, come possiamo sapere se i periodi che non abbiamo scoperto sono veramente impossibili?
Tra 1 e 54 sono note configurazione periodiche per tutti i periodi, ad esclusione di 19, 23, 38, 41 (si guardi qui).
A partire dal 1996, grazie a un metodo proposto da David Buckingham, è possibile realizzare configurazioni periodiche di periodo p per ogni intero p ≥ 54.
Un'altra domanda interessante riguardante il gioco della vita è: una popolazione di cellule può crescere in modo indefinito?
John Conway aveva congetturato che nessuna configurazione iniziale potesse crescere indefinitamente, e aveva offerto 50 dollari in premio a chiunque riuscisse a dimostrarlo.
Ci fu un vincitore sì, ma ciò che aveva scoperto non era proprio ciò che Conway si aspettava.
Nel 1970 Bill Gosper, del MIT, riuscì infatti a trovare una configurazione che sparava triangolini ogni 30 generazioni, senza mai esaurire le munizioni, e smentendo in tal maniera l'ipotesi di Conway.
Fu un vero colpo di fortuna che Gosper, animato evidentemente più da spirito di contraddizione che da sete di denaro, avesse cercato di smentire la congettura piuttosto che provare la sua veridicità.
Se ci avesse infatti provato, non ci sarebbe mai potuto riuscire!
Ecco il video del cannone di alianti di Gosper:


Per capire il principio di tale costruzione, va detto che certe configurazioni hanno la proprietà di spostarsi: dopo un certo numero di tappe nel calcolo, ritorna il medesimo motivo, slittato, come accadrebbe dopo una singola tappa di un automa del tipo Spostamento a Est.
La più semplice fra le configurazioni che si spostano nella maniera descritta è chiamata appunto aliante: in 4 tappe si sposta di una casella in diagonale.

Aliante
Come si può constatare, l'aliante assume ogni volta 4 forme e, al termine delle 4 trasformazioni, si ritrova identico a se stesso spostato di una casella in direzione sud-est.
La velocità di un segnale nel mondo del Game of Life è al massimo di una casella per generazione e per tal ragione viene identificata con la velocità della luce c.
Ne deriva che la velocità dell'aliante è pari a c/4.
Un particolare straordinario sta nel fatto che si possono disporre 13 alianti nel piano in modo tale che dopo che si siano incontrati, quando interagiscono gli uni con gli altri, la configurazione risultante sia un cannone di alianti.


Concludiamo dicendo che usando il Gioco della vita si potrebbe, in teoria, realizzare una macchina di Turing universale, dunque un computer vero e proprio, con memorie e porte logiche, capace di eseguire tutte le operazioni logiche e matematiche che compie un qualsivoglia computer da casa.
Tale considerazione porta con sé un difetto: ogni macchina di Turing è soggetta al cosiddetto "problema della fermata o terminazione".
In altre parole, è impossibile per una qualsiasi macchina di Turing scrivere un algoritmo generale capace di svelarci in anticipo (per tutti i possibili imput) se un dato programma (una data configurazione di celle, nel contesto di Game of Life) alla fine si fermerà o no (cioè se alla fine ci saranno solo caselle vuote).
Un sistema del genere viene detto algoritmicamente indecidibile, ossia la sola maniera per scoprire come si comporta è lasciarlo evolvere.


Alla prossima!

Nessun commento:

Posta un commento