Matemaatika "Elumäng" paljastab kauaotsitud korduvad mustrid | Ajakiri Quanta

1969. aastal töötas Briti matemaatik John Conway välja võluvalt lihtsad reeglid keeruka käitumise loomiseks. Tema elumäng, mida sageli nimetatakse lihtsalt eluks, rullub lahti lõpmatul ruudustikul. Iga rakk võib olla kas "elus" või "surnud". Võre areneb mitme pöörete (või "põlvkondade") jooksul, kusjuures iga lahtri saatuse määravad kaheksa seda ümbritsevat rakku. Reeglid on järgmised:

1. Sünd: surnud rakk, millel on täpselt kolm elavat naabrit, muutub elavaks.
2. Ellujäämine: kahe või kolme elava naabriga rakk jääb ellu.
3. Surm: elusrakk, kellel on vähem kui kaks või rohkem kui kolm elavat naabrit, sureb.

Need lihtsad reeglid loovad hämmastavalt mitmekesise mustrite või "eluvormide" hulga, mis arenevad välja paljudest erinevatest võimalikest ruudustiku algkonfiguratsioonidest. Mängu armastajad on need mustrid aina laienevas järjestuses kokku võtnud ja taksonomiseerinud veebikataloog. Conway avastas mustri, mida nimetatakse vilkuriks ja mis võngub kahe oleku vahel.

Järgmisel aastal leidis ta palju keerulisema mustri nimega pulsar, mis kõigub kolme erineva oleku vahel.

Varsti pärast ostsillaatorite avastamist mõtlesid mängu esimesed uurijad, kas iga perioodi ostsillaatoreid on. "Alguses nägime ainult perioode 1, 2, 3, 4 ja 15," ütles programmeerija ja matemaatik Bill Gosper, kes avastas järgmise paarikümne aasta jooksul 17 erinevat uudset ostsillaatorit. Periood 15 ostsillaatorit (näidatud allpool) tuli juhuslike otsingute käigus üllatavalt sageli esile.

Üllatused ootasid neid, kes olid valmis neid leidma. "Tundide ja päevade vaatamise põhjal tundus 5. periood võimatu," ütles Gosper. Siis 1971. aastal, kaks aastat pärast mängu leiutamist, leiti üks. Uute ostsillaatorite otsimine kasvas mängu peamiseks fookuseks – otsinguks, mida tugevdas arvutitehnoloogia tulek. Kontoriarvutites tehtud varjatud läbiotsimiste aruanded on muutunud mängu folkloori nurgakiviks. "Ettevõtete ja ülikoolide suurarvutitelt varastatud arvutiaja hulk oli jahmatav," ütles Gosper.

1970. aastate jooksul täitsid matemaatikud ja harrastajad teisi lühikesi perioode ja leidsid tükikese pikemaid. Lõpuks avastasid matemaatikud süstemaatilise viisi pika perioodiga ostsillaatorite ehitamiseks. Kuid ostsillaatoreid perioodidega 15–43 oli raske leida. "Inimesed on aastaid püüdnud keskkohta välja mõelda," ütles Maia Karpovitš, Marylandi ülikooli magistrant. Lünkade täitmine sundis teadlasi unistama paljudest uutest tehnikatest, mis nihutasid rakuautomaatide puhul võimalikuks peetud piire, nagu matemaatikud nimetavad arenevaid võre nagu Life.

Nüüd on Karpovitš ja kuus kaasautorit teatanud a Detsembri eeltrükk et nad on leidnud kaks viimast puuduvat perioodi: 19 ja 41. Kui need tühimikud on täidetud, on elu nüüd teadaolevalt "kõikjaperioodiline" – nimetage positiivne täisarv ja eksisteerib muster, mis kordub pärast paljusid samme.

Arenev kogukond, mis on pühendunud elu uurimisele, kuhu kuulub palju teadusmatemaatikuid, aga ka palju harrastajaid, on leidnud peale ostsillaatorite kõikvõimalikke uusi mustreid. Nad on leidnud mustreid, mis liiguvad üle ruudustiku, mida nimetatakse kosmoselaevadeks, ja mustreid, mis loovad muid mustreid: relvad, konstruktorid ja kasvatajad. Nad leidsid mustreid, mis arvutavad algarve, ja isegi mustreid, mis võivad käivitada meelevaldselt keerulisi algoritme.

Ostsillaatoreid, mille perioodid on lühemad kui 15, saab leida käsitsi või elementaarsete algoritmidega, mis otsivad ostsillaatoreid ühe lahtri kaupa. Kuid perioodi kasvades muutub ka keerukus, muutes toore jõuga otsingud palju vähem tõhusaks. "Väikeste perioodide puhul saate otsida otse," ütles Matthias Merzenich, uue artikli kaasautor, kes avastas 31. aastal esimese perioodi-2010 ostsillaatori. "Kuid te ei saa sellest kaugemale minna. Sa ei saa lihtsalt perioodi valida ja seda otsida. (Merzenich teenis 2021. aastal Oregoni osariigi ülikoolis doktorikraadi matemaatikas, kuid töötab praegu farmis.)

1996. aastal näitas Kanada vabakutseline arvutikonsultant ja Life entusiast David Buckingham, kes oli mustreid otsinud alates 1970. aastate lõpust, et 61. ja kõrgema perioodi ostsillaatoreid on võimalik konstrueerida, saates mustri ümber suletud raja lõputus tsüklis. . Kontrollides silmuse pikkust – ja aega, mis mustril ühe edasi-tagasi reisi tegemiseks kulus – leidis Buckingham, et ta saab perioodi muuta nii suureks, kui talle meeldib. "See on keemia ilma naljakate lõhnade või katkiste klaasnõudeta," ütles ta. "Nagu ühendite ehitamine ja seejärel nendevaheliste koostoimete uurimine." See tähendas, et ta oli ühe hoobiga välja mõelnud viisi, kuidas konstrueerida suvaliselt pikkade perioodidega ostsillaatoreid, kui need olid pikemad kui 61.

1990. aastate keskel saadi palju tulemusi, kui paljud puuduvad ostsillaatorid vahemikus 15–61 avastati tuntud ostsillaatorite loominguliste kombinatsioonide kaudu, millele oli antud värvikaid nimesid. Toitlustajad kombineeriti valgusfooridega, vulkaanid sülitasid välja sädemeid ja sööjad sõid purilennukeid.

21. sajandi vahetusel oli silmapaistvaid veel vaid kümmekond perioodi. "See probleem tundus väga võimalik lahendada," ütles Merzenich. 2013. aastal parandas uus avastus nimega Snarki silmus Buckinghami 1996. aasta tehnikat ja alandas piirväärtust, millest kõrgemal oli ostsillaatoreid lihtne konstrueerida, 61-lt 43-le. See jättis puudu vaid viis perioodi. 2019. aastal avastati veel üks ja 2022. aastal veel kaks, jättes alles vaid 19 ja 41 – mõlemad parimad. "Praimid on raskemad, kuna nende konstrueerimiseks ei saa kasutada väikese perioodi ostsillaatoreid," ütles Merzenich.

Mitchell Riley, New Yorgi ülikooli Abu Dhabi järeldoktorant ja teine ​​​​uue artikli kaasautor, on pikka aega olnud huvitatud ostsillaatori tüübist, mida nimetatakse segajaks. "Käsitajate tööviis on see, et teil on keskel aktiivne muster ja väljastpool on stabiilne kraam, mis sellega reageerib," selgitas Riley. Stabiilne materjal, mida nimetatakse katalüsaatoriks, on selleks, et tõugata aktiivne muster tagasi algsesse olekusse.

Nende kujundamine on raske. "Kõik need mustrid on uskumatult haprad, " ütles Riley. "Kui paned ühe punkti paigast ära, siis need tavaliselt lihtsalt plahvatavad."

Riley lõi programmi Barrister, et otsida uusi katalüsaatoreid. "Me otsime natüürmorte, mis on tugevad. Asi on selles, et me tahame, et nad suhtleksid keskel toimuvaga ja seejärel taastuksid, ”ütles Riley.

Riley andis katalüsaatorid, mille Barrister leidis, teises otsinguprogrammis, mis sidus need aktiivsete mustritega. See põhjustas enamasti ebaõnnestumisi, ütles ta. "On üsna haruldane, et üks neist katalüsaatoritest jääb interaktsiooni ellu. Edu garantiid pole. Paned lihtsalt sõrmed risti ja loodad, et saavutad jackpoti. See tundub natuke nagu hasartmäng."

Lõpuks tasus tema panus end ära. Pärast mõnda peaaegu möödalaskmist – ja koodi muutmist, mis laiendas otsingut sümmeetriliste mustritega – leidis ta katalüsaatori interaktsiooni, mis võiks säilitada perioodi 19 ostsillaatorit. "Inimesed olid proovinud igasuguseid tõeliselt keerulisi otsinguid, mille keskel oli palju katalüsaatoreid ja palju haruldasi aktiivseid asju, kuid vaja oli vaid leida see uus turske katalüsaator," ütles Riley.

Viimase puuduva perioodi, 41, leidis teine ​​kaasautor Nicolo Brown, kes on endiselt California ülikooli Santa Cruzi matemaatika bakalaureuseõppes. Brown kasutas katalüsaatoritena purilennukeid, mille idee pakkus esmakordselt välja Merzenich.

"Oleme viimase 10 aasta jooksul avastanud nii palju sügavat käitumist," ütles Karpovitš. „Kõik tähistavad nädal aega – ja siis liiguvad muude asjade juurde. Lahendamiseks on vaja palju muid probleeme. ” Kas antud perioodi ostsillaatoreid saab väiksemaks muuta? Kas on võimalik leida ostsillaatoreid, milles iga rakk võngub? Kas relvi saab valmistada teatud perioodidega? Kas kosmoselaevu saab panna liikuma teatud kiirustel?

Nagu Buckingham ütles: "See on nagu laps lõpmatus mänguasjapoes."