Calcolatori-scacchiera per giocare alla vita

Se cercate un gioco da fare in gruppo, ve ne propongo uno molto semplice. Disponetevi in una fila, in modo che ciascuno si trovi una persona alla sua sinistra e una alla sua destra: faranno eccezione le due persone alle estremità, ciascuna delle quali si ritroverà un solo vicino e non due.
All'inizio del gioco, ognuno deciderà autonomamente se stare in piedi oppure accovacciato. Successivamente, le persone per terra con entrambi i vicini in piedi dovranno alzarsi; viceversa chi si trova in piedi tra due persone accovacciate dovrà a sua volta abbassarsi. In tutti gli altri casi si deve mantenere invariata la propria posizione.
Anche i due giocatori alle estremità dovranno fingere di avere due vicini: quello all'estrema sinistra, con un pizzico di fantasia, dovrà immaginare che il giocatore dell'estrema destra si trovi alla sua sinistra, e viceversa.

Se il gioco viene orchestrato con un buon sincronismo, immagino possa essere divertente: confesso di non averlo mai sperimentato, quindi non prendetevela con me se provandolo lo troverete una cretinata assoluta.
In ogni caso, cretinata o no, lo definirei di una versione "ludico-sociale" di un sistema dinamico discreto noto in matematica e informatica come automa cellulare. L'aggettivo "cellulare" si riferisce al fatto che la griglia regolare sulla quale viene raffigurato il sistema è costituita da celle (che possiamo immaginare quadrate), ciascuna delle quali può assumere un insieme finito di stati. Gli stati di tutte le celle vengono aggiornati contemporaneamente, in passi discreti, cioè generazione dopo generazione.

Nella nostra esemplificazione ludica, le persone recitano il ruolo delle celle, e gli stati possibili sono soltanto due, rappresentati rispettivamente dallo stare in piedi e accovacciati.
In molte implementazioni software, i diversi stati possibili vengono raffigurati tramite colori, cosa che attribuisce a questi automi un particolare fascino scenografico.
Il nostro esempio, che si svolge su una semplice fila di celle-persone, è evidentemente unidimensionale, ma nulla vieta che l’automa possa essere bidimensionale: in questo caso la fila diventa una scacchiera, o se preferite un foglio a quadretti.

Negli automi ad una sola dimensione ogni cella ha, di solito, due celle vicine, ma in alcuni casi si considera un “vicinato” più esteso: è come se, tornando al nostro esempio iniziale, ogni giocatore dovesse tenere conto non soltanto della posizione dei giocatori immediatamente adiacenti, ma anche dei loro vicini, un po’ più a destra e un po’ più a sinistra. Negli automi su scacchiera, per ogni cella si considerano solitamente le otto celle adiacenti che condividono almeno un punto con la cella stessa; ma non sono rari automi in cui ciascuna il vicinato è formato soltanto dalle quattro celle che hanno in comune almeno un lato con la cella in questione.
Come avrete capito, la scelta del vicinato è fondamentale nella progettazione di un automa cellulare, perché essa determina le variabili che ogni cella deve tenere in considerazione per decidere come evolvere ad ogni passo.
Una volta definito il vicinato di ogni cella, occorre stabilire le regole di evoluzione. Nell’esempio iniziale, dato che ogni cella ha due vicini, si tratta di considerare le otto possibili combinazioni di stati per tre celle, e associare a ciascuna uno stato futuro per la cella centrale. La figura a fianco sintetizza la regola scelta (0 e 1 indicano rispettivamente le due possibili posizioni dei giocatori, in piedi o accovacciati).

È evidente che questa non è l’unica regola possibile. Quante diverse regole esistono, considerando vicinati di tre celle? Le possibili configurazioni di stati di tre celle sono 23 = 8, e i modi in cui a queste otto configurazioni possono corrispondere stati futuri sono 28 = 256.

Quindi esistono in tutto 256 automi cellulari unidimensionali: essendo tutto sommato pochi, gli studiosi li trattano quasi come dei figli (per dirla alla partenopea, piezz’ e core), al punto che hanno dato un nome a ciascuno di loro.
Un po’ come un appassionato biologo marino che abbia catalogato tutte le specie di cetacei che vivono in un certo arcipelago. Bè, adesso non immaginatevi nomi molto fantasiosi: sono semplicemente i numeri da 1 a 256. Per la cronaca, il divertentissimo gioco che vi ho proposto all’inizio del post utilizza la regola n. 232.

E a due dimensioni? Bè, se consideriamo vicinati “classici” da 8 celle, si ottengono in tutto 29 = 512 combinazioni di stati per vicinato, e quindi 2512 regole: se lo scrivessimo per esteso sarebbe un numero enorme, di 154 cifre. Un po’ troppe per i miei gusti.

I pionieri degli automi cellulari furono il matematico polacco Stanislaw Ulam e il matematico ungherese naturalizzato statunitense John von Neumann, che vediamo nella foto a lato in compagnia del grande fisico americano Richard Feynman (Ulam è a sinistra, von Neumann a destra).
Subito dopo la fine della seconda guerra mondiale, Ulam e von Neumann (che avevano entrambi avuto un ruolo determinante nel famigerato progetto Manhattan, che portò alla realizzazione delle prime bombe atomiche) si proposero di definire modelli matematici in grado di rappresentare la complessità dei fenomeni biologici, con particolare interesse per i meccanismi di crescita e riproduzione degli esseri viventi.
Con l'avanzare dell'informatica teorica e delle tecnologie di computazione, la teoria degli automi cellulari fiorì e attirò l'attenzione di molti studiosi di primo livello.

Nel 1970 un particolare automa cellulare apparve sulla rivista "Scientific American", nella famosa rubrica "Mathematical Games" di Martin Gardner: era il famoso "Gioco della Vita" ("Game of Life"), ideato dal matematico e grande divulgatore inglese John Conway per rappresentare i meccanismi di sviluppo e auto-organizzazione tipici degli organismi viventi. Ben presto la creazione di Conway divenne l'esempio più celebre di automa cellulare, nonché il capostipite di molti altri automi più o meno complessi e fantasiosi.
Nella sua versione classica, il Gioco della Vita si compone di una scacchiera di celle in cui ogni cella ha 8 vicini e può assumere 2 stati (viva o morta). Le regole sono due: una cella morta con 3 vicini vivi diventa viva, mentre una cella viva con meno di 2 o più di 3 vicini vivi muore (rispettivamente per isolamento o per soffocamento).

Fiumi di inchiostro (e di bit) sono stati versati sul Gioco della Vita: una ricerca sul web vi permetterà di scoprire sorprendenti meraviglie su questo automa.
Chi comincia a trastullarsi con il sistema di Conway scopre ben presto che esistono particolari configurazioni che, in base alle semplici regole del gioco, si comportano in modo speciale: alcune oscillano indefinitamente tra due stati estremi, altre si spostano attraverso la scacchiera, altre ancora sono stabili e immutabili, altre ancora si evolvono per molte generazioni e poi ripetono lo stesso ciclo di trasformazioni. Esistono perfino gruppi di celle stabili che sparano proiettili. E così via, in un fantastico bestiario di strane creature matematiche.

Uno degli aspetti più importanti a livello teorico è il fatto che il Gioco della Vita, dotata delle regole sopra esposte, ha la stessa potenza di calcolo di un qualsiasi computer: detto in altro modo, è Turing-completa, o equivalente ad una macchina di Turing universale.  Qualsiasi calcolo che possa essere eseguito da un algoritmo, insomma, può essere eseguito in qualche modo sulla scacchiera di Conway.

La rivista "Scientific American" è sempre stata particolarmente attenta agli automi cellulari. Conservo ancora un numero del 1989 nel quale un articolo di Alexander Dewdney (nella indimenticata rubrica “(Ri)creazioni al calcolatore”) descriveva un altro bellissimo automa cellulare, ideato da David Griffeath e denominato "spazio ciclico".
L'automa è composto da una griglia di celle che possono assumere un certo numero di stati, rappresentati tipicamente da colori diversi e disposti in una successione ordinata. Gli stati iniziali sono del tutto casuali; successivamente, se una cella ha un vicino il cui stato è il successivo del proprio, allora la cella viene "mangiata" e assume lo stato del vicino. (Si tenga presente che l'aritmetica utilizzata, sia per gli stati che per la geometria delle celle è modulare, cioè è la cosiddetta "aritmetica dell'orologio", in cui il successore dell'ultimo numero disponibile è lo zero).

Ricordo, come fosse ieri, che appena lessi quell'articolo provai subito a implementare l'algoritmo sul mio personal computer (credo in Pascal), e rimasi affascinato (ma dovrei dire forse stregato, o incantato) dal constatare come una regola apparentemente così semplice e banale potesse generare, con il trascorrere delle generazioni, configurazioni di grande bellezza e ordine, come potete vedere nella figura sopra.
Emozioni come quelle segnano irrimediabilmente chi le ha provate (non so se nel bene o nel male). Anzi, adesso che ci penso, devo andare a cercare quel programmino scritto tanti anni fa: chissà che non funzioni ancora dopo tanti anni...

Commenti

  1. Bello questo post sugli automi cellulari, molto fantasioso. Mi piace come spieghi e scrivi!

    RispondiElimina

Posta un commento