Mathova 'Igra življenja' razkriva dolgo iskane ponavljajoče se vzorce | Revija Quanta

Leta 1969 je britanski matematik John Conway zasnoval osupljivo preprost niz pravil za ustvarjanje zapletenega vedenja. Njegova Igra življenja, pogosto imenovana preprosto Življenje, se odvija na neskončni kvadratni mreži celic. Vsaka celica je lahko "živa" ali "mrtva". Mreža se razvija skozi niz obratov (ali "generacij"), pri čemer usodo vsake celice določa osem celic, ki jo obkrožajo. Pravila so naslednja:

1. Rojstvo: Mrtva celica z natanko tremi živimi sosedi postane živa.
2. Preživetje: Živa celica z dvema ali tremi živimi sosedi ostane živa.
3. Smrt: živa celica z manj kot dvema ali več kot tremi živimi sosedi umre.

Ta preprosta pravila ustvarjajo osupljivo raznoliko paleto vzorcev ali "oblik življenja", ki se razvijejo iz številnih različnih možnih začetnih konfiguracij mreže. Ljubitelji igre so sešteli in taksonomizirali te vzorce v vedno večjem obsegu spletni katalog. Conway je odkril vzorec, imenovan blinker, ki niha med dvema stanjema.

Naslednje leto je našel veliko bolj zapleten vzorec, imenovan pulsar, ki niha med tremi različnimi stanji.

Kmalu po odkritju oscilatorjev so se prvi raziskovalci igre spraševali, ali obstajajo oscilatorji vseh obdobij. "Sprva smo videli samo obdobja 1, 2, 3, 4 in 15," je dejal računalniški programer in matematik Bill Gosper, ki je v naslednjih nekaj desetletjih odkril 17 različnih novih oscilatorjev. Oscilatorji 15. obdobja (prikazani spodaj) so se presenetljivo pogosto pojavljali pri naključnih iskanjih.

Na tiste, ki so jih bili pripravljeni najti, so čakala presenečenja. "Po urah in dneh gledanja se je peto obdobje zdelo nemogoče," je dejal Gosper. Leta 5, dve leti po iznajdbi igre, so enega našli. Lov na nove oscilatorje je prerasel v glavno središče igre, iskanje, ki ga je okrepil prihod računalniške tehnologije. Računi o tajnih preiskavah, opravljenih na pisarniških računalnikih, so postali temelj folklore igre. "Količina računalniškega časa, ukradenega iz velikih računalnikov podjetij in univerz, je bila osupljiva," je dejal Gosper.

Skozi sedemdeseta leta prejšnjega stoletja so matematiki in ljubitelji zapolnili druga kratka obdobja in odkrili nekaj daljših. Sčasoma so matematiki odkrili sistematičen način za izdelavo dolgoperiodičnih oscilatorjev. Toda oscilatorje s periodami med 1970 in 15 se je izkazalo za težko najti. "Ljudje že leta poskušajo ugotoviti sredino," je dejal Maja Karpovič, podiplomski študent na Univerzi v Marylandu. Zapolnjevanje vrzeli je prisililo raziskovalce, da so izmislili množico novih tehnik, ki so premikale meje tega, kar se je zdelo mogoče s celičnimi avtomati, kot matematiki imenujejo razvijajoče se mreže, kot je življenje.

Zdaj so Karpovich in šest soavtorjev objavili v a decembrski prednatis da so našli zadnji dve manjkajoči piki: 19 in 41. Ko so te vrzeli zapolnjene, je zdaj znano, da je Življenje "omniperiodično" - poimenujte pozitivno celo število in obstaja vzorec, ki se ponovi po toliko korakih.

Rastoča skupnost, posvečena preučevanju življenja, ki vključuje številne matematike raziskovalce, pa tudi številne hobiste, ni našla le oscilatorjev, ampak vse vrste novih vzorcev. Našli so vzorce, ki potujejo po mreži, imenovane vesoljske ladje, in vzorce, ki gradijo druge vzorce: puške, konstruktorji in rejci. Našli so vzorce, ki izračunavajo praštevila, in celo vzorce, ki lahko izvajajo poljubno zapletene algoritme.

Oscilatorje s periodami, krajšimi od 15, je mogoče najti ročno ali z osnovnimi algoritmi, ki iščejo oscilatorje eno celico naenkrat. Ko pa se obdobje daljša, se veča tudi zapletenost, zaradi česar je iskanje na silo veliko manj učinkovito. »Za majhna obdobja lahko iščete neposredno,« je dejal Matthias Merzenich, soavtor novega članka, ki je leta 31 odkril prvi oscilator periode 2010. »Ampak dlje od tega ne morete iti. Ne moreš kar izbrati obdobja in ga iskati.« (Merzenich je leta 2021 doktoriral iz matematike na državni univerzi Oregon, trenutno pa dela na kmetiji.)

Leta 1996 je David Buckingham, kanadski samostojni računalniški svetovalec in navdušenec nad življenjem, ki je vzorce iskal že od poznih sedemdesetih let prejšnjega stoletja, pokazal, da je mogoče izdelati oscilatorje s periodo 1970 in višje s pošiljanjem vzorca po zaprti stezi v neskončni zanki. . Z nadzorovanjem dolžine zanke - in časa, ki je bil potreben za dokončanje ene povratne vožnje - je Buckingham ugotovil, da lahko poveča obdobje, kolikor hoče. "To je kemija brez smešnih vonjav ali zlomljene steklovine," je dejal. "Kot gradnja spojin in nato raziskovanje interakcij med njimi." To je pomenilo, da se je z enim zamahom domislil, kako konstruirati oscilatorje poljubno dolgih period, če so bile daljše od 61.

Sredi devetdesetih let prejšnjega stoletja je bilo veliko rezultatov, ko je bilo veliko manjkajočih oscilatorjev med 1990 in 15 odkritih s kreativnimi kombinacijami znanih oscilatorjev, ki so jim dali vrsto barvitih imen. Gostince so kombinirali s semaforji, vulkani so bruhali iskre, jedci pa so jedli jadralna letala.

Do preloma v 21. stoletje je bilo odprtih le še ducat obdobij. "Zdelo se je zelo mogoče rešiti ta problem," je dejal Merzenich. Leta 2013 je novo odkritje, imenovano Snarkova zanka, izboljšalo Buckinghamovo tehniko iz leta 1996 in znižalo mejo, nad katero je bilo enostavno sestaviti oscilatorje, z 61 na 43. To je pustilo samo pet manjkajočih obdobij. Leta 2019 so odkrili še enega, leta 2022 pa še dva, tako da jih je ostalo le še 19 in 41 – oba vrhunska. "Praštevila so težja, ker za njihovo izdelavo ne morete uporabiti oscilatorjev z majhno periodo," je dejal Merzenich.

Mitchell Riley, podoktorski raziskovalec na newyorški univerzi Abu Dhabi in drugi soavtor novega prispevka, je že dolgo zanimal vrsta oscilatorja, imenovanega hassler. »Napadalci delujejo tako, da imate aktiven vzorec na sredini in nekaj stabilnih stvari na zunanji strani, ki reagirajo z njim,« je pojasnil Riley. Stabilna snov, imenovana katalizator, je tam, da potisne aktivni vzorec nazaj v prvotno stanje.

Oblikovanje jih je težko. "Vsi ti vzorci so neverjetno krhki," je dejal Riley. "Če postavite eno samo piko na svoje mesto, običajno eksplodira."

Riley je ustvaril program, imenovan Barrister, za iskanje novih katalizatorjev. »Kar iščemo, so tihožitja, ki so robustna. Bistvo je v tem, da želimo, da sodelujejo s tem, kar se dogaja na sredini, in si nato opomorejo,« je dejal Riley.

Riley je katalizatorje, ki jih je našel Barrister, vnesel v drug iskalni program, ki jih je združil z aktivnimi vzorci. To je večinoma vodilo do neuspehov, je dejal. "Precej redko je, da eden od teh katalizatorjev preživi interakcijo. Ni zagotovila za uspeh. Samo držiš pesti in upaš, da boš zadel jackpot. Zdi se mi kot igranje iger na srečo.«

Na koncu se je njegova stava izplačala. Po nekaj skorajšnjih napakah - in spremembi kode, ki je razširila iskanje na simetrične vzorce - je našel interakcijo katalizatorja, ki bi lahko vzdrževala oscilator periode 19. "Ljudje so preizkušali vse vrste res zapletenih iskanj z veliko katalizatorji in veliko redkimi aktivnimi stvarmi na sredini, a vse, kar je bilo potrebno, je bilo najti ta nov kruti katalizator," je dejal Riley.

Zadnjo manjkajočo piko, 41, je našel Nicolo Brown, drugi soavtor, ki še vedno študira matematiko na kalifornijski univerzi v Santa Cruzu. Brown je kot katalizatorje uporabil jadralna letala, idejo, ki jo je prvi predlagal Merzenich.

"V zadnjih 10 letih smo odkrili toliko globokega vedenja," je dejal Karpovich. »Vsi praznujejo en teden - nato pa se premaknejo k drugim stvarem. Toliko drugih težav je treba rešiti.« Ali je mogoče oscilatorje določene periode zmanjšati? Ali lahko najdemo oscilatorje, v katerih niha vsaka posamezna celica? Ali je mogoče izdelati puške z določenimi obdobji? Ali je mogoče narediti vesoljske ladje za potovanje z določeno hitrostjo?

Kot je rekel Buckingham, "je kot otrok v neskončni trgovini z igračami."