Il "gioco della vita" della matematica rivela schemi ripetuti a lungo ricercati | Rivista Quanti

Nel 1969, il matematico britannico John Conway ideò un insieme di regole incredibilmente semplici per creare comportamenti complessi. Il suo Gioco della Vita, spesso definito semplicemente Vita, si svolge su un'infinita griglia quadrata di celle. Ogni cellula può essere “viva” o “morta”. La griglia si evolve in una serie di turni (o “generazioni”), con il destino di ciascuna cella determinato dalle otto celle che la circondano. Le regole sono le seguenti:

1. Nascita: una cellula morta con esattamente tre vicini vivi diventa viva.
2. Sopravvivenza: una cellula viva con due o tre vicini vivi rimane viva.
3. Morte: una cellula viva con meno di due o più di tre vicini vivi muore.

Queste semplici regole creano una gamma sorprendentemente diversificata di modelli, o “forme di vita”, che si evolvono dalle molte diverse possibili configurazioni iniziali della griglia. Gli amanti del gioco hanno conteggiato e tassonomizzato questi modelli in continua espansione catalogo online. Conway ha scoperto uno schema chiamato lampeggiante, che oscilla tra due stati.

L'anno successivo scoprì uno schema molto più complicato chiamato pulsar, che oscilla tra tre stati diversi.

Subito dopo la scoperta degli oscillatori, i primi esploratori del gioco si chiesero se esistessero oscillatori di ogni periodo. "All'inizio vedevamo solo i periodi 1, 2, 3, 4 e 15", ha detto il programmatore di computer e matematico Bill Gosper, che avrebbe scoperto 17 diversi nuovi oscillatori nel corso dei decenni successivi. Gli oscillatori del periodo 15 (mostrati sotto) sono emersi sorprendentemente spesso nelle ricerche casuali.

Le sorprese erano in agguato per coloro che erano disposti a trovarle. "Dalle ore e dai giorni di visione, il periodo 5 sembrava impossibile", ha detto Gosper. Poi nel 1971, due anni dopo l'invenzione del gioco, ne fu trovato uno. La ricerca di nuovi oscillatori è diventata uno degli obiettivi principali del gioco, una ricerca rafforzata dall'avvento della tecnologia informatica. I resoconti di ricerche segrete condotte sui computer dell'ufficio sono diventati una pietra miliare del folklore del gioco. "La quantità di tempo rubato ai mainframe aziendali e universitari è stata sconcertante", ha affermato Gosper.

Nel corso degli anni settanta, matematici e hobbisti riempirono gli altri periodi brevi e trovarono un'infarinatura di periodi più lunghi. Alla fine, i matematici scoprirono un modo sistematico per costruire oscillatori a lungo periodo. Ma gli oscillatori con periodi compresi tra 1970 e 15 si sono rivelati difficili da trovare. "Le persone hanno cercato di trovare la via di mezzo per anni", ha detto Maia Karpovich, uno studente laureato presso l'Università del Maryland. Colmare le lacune ha costretto i ricercatori a inventare una serie di nuove tecniche che hanno ampliato i confini di ciò che si riteneva possibile con gli automi cellulari, come i matematici chiamano griglie in evoluzione come la Vita.

Ora Karpovich e sei coautori hanno annunciato in a Prestampa di dicembre che hanno trovato gli ultimi due periodi mancanti: 19 e 41. Una volta colmate queste lacune, ora sappiamo che la Vita è “omniperiodica” – nomina un numero intero positivo, ed esiste uno schema che si ripete dopo tanti passaggi.

La fiorente comunità dedita allo studio della Vita, che comprende molti matematici ricercatori ma anche molti hobbisti, ha trovato non solo oscillatori ma tutti i tipi di nuovi modelli. Hanno trovato modelli che viaggiano attraverso la griglia, soprannominati astronavi e modelli che costruiscono altri modelli: pistole, costruttori e allevatori. Hanno trovato modelli che calcolano i numeri primi e persino modelli che possono eseguire algoritmi arbitrariamente complicati.

Gli oscillatori con periodi inferiori a 15 possono essere trovati manualmente o con algoritmi rudimentali che cercano gli oscillatori una cella alla volta. Ma man mano che il periodo diventa più lungo, aumenta anche la complessità, rendendo le ricerche di forza bruta molto meno efficaci. “Per piccoli periodi, puoi cercare direttamente”, ha detto Matthias Merzenich, coautore del nuovo articolo che ha scoperto il primo oscillatore del periodo 31 nel 2010. “Ma non puoi davvero andare oltre. Non puoi semplicemente scegliere un periodo e cercarlo. (Merzenich ha conseguito il dottorato in matematica presso la Oregon State University nel 2021, ma attualmente lavora in una fattoria.)

Nel 1996, David Buckingham, un consulente informatico freelance canadese e appassionato di Life che era alla ricerca di schemi sin dalla fine degli anni '1970, ha dimostrato che era possibile costruire oscillatori del periodo 61 e superiore inviando uno schema attorno a una traccia chiusa in un ciclo infinito. . Controllando la lunghezza del ciclo – e il tempo impiegato dallo schema per completare un viaggio di andata e ritorno – Buckingham scoprì che poteva ampliare il periodo quanto desiderava. "È chimica senza odori strani o bicchieri rotti", ha detto. "Come costruire composti e poi esplorare le interazioni tra loro." Ciò significava che, in un colpo solo, aveva escogitato un modo per costruire oscillatori di periodi arbitrariamente lunghi, purché fossero più lunghi di 61.

Ci furono una serie di risultati a metà degli anni '1990, quando molti degli oscillatori mancanti tra 15 e 61 furono scoperti attraverso combinazioni creative di oscillatori conosciuti, a cui erano stati dati una serie di nomi coloriti. I ristoratori si univano ai semafori, i vulcani sputavano scintille e i mangiatori mangiavano alianti.

All’inizio del 21° secolo, solo una dozzina di periodi erano ancora in sospeso. "Sembrava molto possibile risolvere questo problema", ha detto Merzenich. Nel 2013, una nuova scoperta chiamata anello Snark ha migliorato la tecnica di Buckingham del 1996 e ha abbassato il limite sopra il quale era facile costruire oscillatori da 61 a 43. Ciò ha lasciato solo cinque periodi mancanti. Un altro è stato scoperto nel 2019 e altri due nel 2022, lasciando solo 19 e 41, entrambi primi. “I numeri primi sono più difficili perché non è possibile utilizzare oscillatori di piccolo periodo per costruirli”, ha detto Merzenich.

Mitchell Riley, ricercatore post-dottorato presso la New York University Abu Dhabi e altro coautore del nuovo articolo, è da tempo incuriosito da un tipo di oscillatore chiamato hassler. "Il modo in cui funzionano gli scocciatori è che hai uno schema attivo nel mezzo e alcune cose stabili all'esterno che reagiscono con esso", ha spiegato Riley. La sostanza stabile, chiamata catalizzatore, è lì per riportare il modello attivo al suo stato originale.

Progettarli è difficile. "Tutti questi modelli sono incredibilmente fragili", ha detto Riley. "Se metti un singolo punto fuori posto, di solito esplode."

Riley ha creato un programma chiamato Barrister per cercare nuovi catalizzatori. “Ciò che cerchiamo sono nature morte robuste. Il punto è che vogliamo che interagiscano con ciò che sta accadendo nel mezzo e poi si riprendano”, ha detto Riley.

Riley ha alimentato i catalizzatori che l'avvocato ha trovato in un altro programma di ricerca che li ha accoppiati con modelli attivi. Ciò ha portato per lo più a fallimenti, ha detto. “È abbastanza raro che uno di questi catalizzatori sopravviva all’interazione. Non c’è garanzia di successo. Incroci semplicemente le dita e speri di vincere il jackpot. Sembra un po’ come giocare d’azzardo”.

Alla fine, la sua scommessa ha dato i suoi frutti. Dopo alcuni incidenti mancati – e una modifica al codice che ha ampliato la ricerca per includere modelli simmetrici – ha trovato un’interazione catalizzatrice che potrebbe sostenere un oscillatore del periodo 19. "Le persone hanno provato tutti i tipi di ricerche davvero complicate con molti catalizzatori e molte cose attive rare nel mezzo, ma tutto ciò che era necessario era trovare questo nuovo grosso catalizzatore", ha detto Riley.

L'ultimo punto mancante, 41, è stato trovato da Nicolo Brown, un altro coautore, che studia ancora matematica all'Università della California, a Santa Cruz. Brown usò gli alianti come catalizzatori, un'idea proposta per la prima volta da Merzenich.

"Abbiamo scoperto comportamenti così profondi negli ultimi 10 anni", ha detto Karpovich. “Tutti festeggiano per una settimana e poi passano ad altre cose. Ci sono tanti altri problemi da risolvere”. È possibile ridurre gli oscillatori di un dato periodo? Si possono trovare oscillatori in cui ogni singola cellula oscilla? Si possono realizzare armi con periodi particolari? È possibile far viaggiare le astronavi a velocità particolari?

Come ha detto Buckingham, “È come essere un bambino in un negozio di giocattoli infinito”.