Trovato la vita divina – NRC

Un giorno d’estate del 1992, il matematico britannico John Conway (1937-2020) ha inviato un’e-mail a un amico. Chiedi se c’è Gioco della vita C’è una “natura morta divina”. Con questo intendeva una formazione stabile che non poteva evolversi, ma faceva sempre parte dello stato iniziale del gioco. Conway ha concluso dicendo che avrebbe “preso un hot dog ora” e che il messaggio potrebbe “essere distribuito ulteriormente se lo si desidera”.

Leggi anche: Il matematico Conway era un genio giocoso e un conoscitore della simmetria

Il gioco della vita ha reso Conway famoso nel mondo negli anni 70. Gli studenti di informatica sono diventati dipendenti dalla programmazione delle regole del gioco della vita. All’inizio degli anni ’70, una newsletter, Lifeline, fu distribuita ai matematici e fu attesa con impazienza. Nel numero di ottobre 1972 È stata posta anche la domanda di Conway sulla “natura morta divina”, in termini leggermente diversi. Non c’è dubbio che le email del 1992 siano finite nelle caselle di posta di molti. Ma non c’era sempre una risposta. Finora: Phil Salo e Ilka Turma, due ricercatori post-dottorato della Facoltà di Matematica dell’Università di Turku in Finlandia, hanno risolto il problema.

Il gioco della vita è, nelle parole di Conway, “un gioco senza giocatori che non finisce mai”. Il punto di partenza è una rete infinita le cui celle possono essere “vive” o “morte”. Ogni cella contiene otto vicini: quattro celle sono adiacenti perpendicolarmente e quattro sono adiacenti in diagonale. Colora in alcune scatole: queste sono cellule viventi. Le cellule rimanenti sono morte. Questa è Generazione Zero. Ora Conway applica “leggi genetiche” accuratamente selezionate. Primo: una cellula vivente con due o tre vicini viventi sopravvive nella generazione successiva, altrimenti muore. Secondo: una cellula morta con esattamente tre vicini viventi diventa viva nella generazione successiva, altrimenti rimane morta.

Sulla base della generazione zero autoidentificata, hai un computer di prima generazione, quindi una seconda generazione e così via. Come si comporta il modello? Sebbene le regole per la sopravvivenza, la morte e la rinascita siano semplici, è difficile prevedere cosa farà qualsiasi configurazione iniziale. Tutte le cellule viventi scompaiono a un certo punto, lasciando dietro di sé una rete morta? Lo schema iniziale porta a uno schema ripetuto? Può crescere per sempre? Tutto questo è possibile, ma non c’è modo di saperlo in generale.

modelli obliqui

L’elemento di gioco del Game of Life riguarda principalmente la ricerca di schemi che si evolvono in modo interessante. O, al contrario, schemi che non si sviluppano, le cosiddette “nature morte”: questi schemi restano immutati in ogni generazione successiva. L’esempio più semplice è un quadrato di due in due celle vive. Subito dopo che Conway concepì il gioco della vita, furono scoperte diverse nature morte. Tutti avevano in comune il fatto di avere stili diversi nelle generazioni precedenti. A meno che, ovviamente, tu non scelga una natura morta come Generation Zero.

Il problema di Conway su “Divine Fixed Spirits” non è correlato agli schemi in futuro Sarà sempre lì, ma quelli dentro passato È sempre stato: ci sono schemi che possono derivare solo da qualsiasi configurazione da soli? A gennaio, Salo e Turma hanno fornito una risposta modificata: Sì, tali schemi esistono.

I finlandesi pubblicano la loro scoperta in un forum dedicato a Game of Life. Nell’illustrazione mostrata, le cellule blu sono vive e i leucociti sono morti. La condizione delle celle grigie non ha importanza. “Se questo modello si verifica in una particolare generazione, è già presente nella generazione precedente”. Questa è l’affermazione provata da Salò e Turma. In altre parole, non c’è formazione iniziale senza un modello Salo e Törmä, poiché si sviluppa in una formazione con questo modello.

Molto debole

Tuttavia, ciò non significa che se la configurazione iniziale contiene il pattern, quel pattern rimarrà sempre. Via e-mail, Turma afferma: “È un modello molto fragile che si rompe facilmente. Ma aggiungendo alcune cellule viventi extra ai bordi, il modello può essere espanso in natura morta”. L’estensione trovata da Salò e Torma è composta da 116 cellule viventi. Questo numero è stato rapidamente ridotto a 48 da Oscar Cunningham, un ingegnere di dati dalla Gran Bretagna: Nell’illustrazione, fai vivere 48 celle grigie con una croce blu e avrai una natura morta. Turma: “Una natura morta in sé non è speciale, ma una natura morta che contiene uno schema che deve essere apparso in tutte le generazioni precedenti lo è.”

Nella loro ricerca, i matematici hanno utilizzato SAT-solver, un programma per computer che risolve problemi le cui soluzioni sono facili da controllare, ma non necessariamente da trovare. Ad esempio, considera il gioco Sudoku. Törmä: „Abbiamo dato al risolutore SAT un pattern P e gli abbiamo chiesto di trovare un altro pattern Q simile a P nella prossima generazione, o di dimostrare che un Q like non esiste. Se il parser SAT fa una domanda del genere, è facile verificare se si evolve in una P, ma non esiste un modo ovvio per trovare la Q.”