Scoperta di una natura morta divina – NRC

Un giorno d’estate del 1992, il matematico britannico John Conway (1937-2020) ha inviato un’e-mail a un collega amico. Ha chiesto se c’era Il gioco della vita esiste una “natura morta divina”. Con questo intendeva una configurazione stabile che non avrebbe potuto essere ridimensionata, ma era ancora parte dello stato iniziale del gioco. Conway ha concluso dicendo che “avrebbe preso un hot dog ora” e il messaggio potrebbe essere “più ampiamente distribuito se desiderato”.

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

Game of Life ha reso Conway famoso in tutto il mondo nel 1970. 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 ed era molto attesa. Nel numero di ottobre 1972 È stata posta anche la domanda di Conway sulle “nature morte divine” – in termini leggermente diversi. E l’e-mail del 1992 senza dubbio è finita nelle caselle di posta di molti. Ma non c’era ancora risposta. Finora: Ville Salo e Ilkka Törmä, due dottorandi della Facoltà di Matematica dell’Università di Turku in Finlandia, hanno risolto il problema.

Game of Life è – nelle stesse parole di Conway – un “gioco senza giocatori senza fine”. Il punto di partenza è una griglia infinita le cui celle possono essere “vive” o “morte”. Ogni cella ha otto vicini: quattro celle adiacenti ortogonalmente e quattro celle adiacenti diagonalmente. Colora alcuni quadrati: queste sono le cellule viventi. Le altre cellule sono morte. È la generazione zero. Applica ora le “leggi genetiche” scelte con cura da Conways. Uno: una cellula vivente che ha due o tre vicini viventi rimane in vita nella generazione successiva, altrimenti muore. Due: una cellula morta con esattamente tre vicini viventi diventa viva nella generazione successiva, altrimenti rimane morta.

Basato su una generazione zero auto-selezionata, fai in modo che un computer disegni la prima generazione, quindi la seconda generazione e così via. Come si comporta il modello? Sebbene le regole di sopravvivenza, morte e nascita siano semplici, è difficile prevedere cosa farà qualsiasi configurazione iniziale. Tutte le cellule viventi scompaiono a un certo punto, lasciando dietro di sé una griglia morta? Il motivo originale porta a un motivo ripetuto? Può crescere per sempre? Tutto è possibile, ma non c’è modo di saperlo in generale.

Modelli divergenti

L’elemento di gioco in Game of Life riguarda principalmente la ricerca di modelli che si sviluppano in modi interessanti. O, al contrario, schemi che non si sviluppano, detti “nature morte”: questi rimangono immutati ad ogni generazione successiva. L’esempio più semplice è un quadrato di celle viventi due per due. Poco dopo che Conway progettò Game of Life, furono scoperte molte nature morte. Tutti avevano in comune il fatto di avere modelli diversi nelle generazioni precedenti. A meno che, ovviamente, tu non scelga una natura morta come la generazione zero.

Il problema di Conway con le “nature morte divine” non riguarda i modelli che vi si trovano futuro esisterà sempre, ma coloro che esistono nel passaggio sono sempre stati: ci sono motivi che non possono nascere da nessuna configurazione se non da se stessi? A gennaio, Salo e Törmä hanno trovato la risposta liberatoria: sì, tali schemi esistono.

I finlandesi pubblicano la loro scoperta su un forum dedicato al Gioco della Vita. Nell’illustrazione mostrata, le cellule blu sono vive, quelle bianche sono morte. Lo stato delle celle grigie non ha importanza. “Se questo modello si verifica in una certa generazione, allora era già presente nella generazione precedente”. Questa è l’affermazione che Salo e Törmä hanno dimostrato. In altre parole, non c’è configurazione iniziale senza il modello di Salò e Törmä, evolvendosi verso una configurazione con questo modello.

molto vulnerabile

Tuttavia, ciò non significa che se una configurazione iniziale contiene il modello, quel modello sopravviverà sempre. Via e-mail, Törmä afferma: “È un modello molto fragile che collassa facilmente. Ma aggiungendo alcune altre cellule viventi attorno ai bordi, il modello può essere esteso a una natura morta. L’estensione scoperta da Salò e Törmä consisteva in 116 cellule viventi. Questo numero è stato rapidamente ridotto a 48 da Oscar Cunningham, un ingegnere di dati britannico: nell’illustrazione, dai vita alle 48 celle grigie con una croce blu e avrai una natura morta. Törmä: “Le nature morte in sé non sono speciali, ma una natura morta che contiene un motivo che deve essere apparso in tutte le generazioni precedenti lo è.”

Nella loro ricerca, i matematici hanno utilizzato un “SAT-solver”, un programma per computer che risolve problemi le cui soluzioni sono facili da verificare, ma non necessariamente da trovare. Ad esempio, considera un sudoku. Törmä: “Abbiamo fornito al risolutore SAT un modello P e gli abbiamo chiesto di trovare un altro modello Q che assomigli a P nella prossima generazione, o di dimostrare che tale Q non esiste. Se il risolutore SAT fornisce una tale Q, è è facile verificare se evolve in P, ma non esiste un modo chiaro per trovare Q.