Math's Game of Life paljastaa kauan kaivattuja toistuvia kuvioita | Quanta-lehti

Vuonna 1969 brittiläinen matemaatikko John Conway kehitti hämmästyttävän yksinkertaiset säännöt monimutkaisen käyttäytymisen luomiseksi. Hänen elämänpelinsä, jota usein kutsutaan yksinkertaisesti elämäksi, avautuu äärettömässä solujen neliöruudukossa. Jokainen solu voi olla joko "elossa" tai "kuollut". Ruudukko kehittyy kierrosten (tai "sukupolvien") aikana, ja kunkin solun kohtalon määrää sitä ympäröivät kahdeksan solua. Säännöt ovat seuraavat:

1. Syntymä: Kuollut solu, jossa on tasan kolme elävää naapuria, herää eloon.
2. Selviytyminen: Elävä solu, jossa on kaksi tai kolme elävää naapuria, pysyy hengissä.
3. Kuolema: Elävä solu, jossa on vähemmän kuin kaksi tai enemmän kuin kolme elävää naapuria, kuolee.

Nämä yksinkertaiset säännöt luovat hämmästyttävän monipuolisen joukon kuvioita tai "elämän muotoja", jotka kehittyvät ruudukon monista mahdollisista aloituskonfiguraatioista. Pelin ystävät ovat laskeneet ja taksonomisoineet nämä mallit jatkuvasti laajenevassa muodossa online-luettelo. Conway löysi kuvion nimeltä vilkku, joka värähtelee kahden tilan välillä.

Seuraavana vuonna hän löysi paljon monimutkaisemman kuvion nimeltä pulsar, joka värähtelee kolmen eri tilan välillä.

Pian sen jälkeen, kun oskillaattorit löydettiin, pelin varhaiset tutkijat ihmettelivät, onko jokaiselle ajanjaksolle olemassa oskillaattorit. "Aluksi näimme vain jaksot 1, 2, 3, 4 ja 15", sanoi tietokoneohjelmoija ja matemaatikko Bill Gosper, joka aikoi löytää 17 erilaista uutta oskillaattoria seuraavien vuosikymmenten aikana. Periodi 15 oskillaattoria (näkyy alla) tuli yllättävän usein esiin satunnaisissa hauissa.

Yllätykset odottivat niitä, jotka halusivat löytää ne. "Tuntien ja päivien katselun perusteella jakso 5 vaikutti mahdottomalta", Gosper sanoi. Sitten vuonna 1971, kaksi vuotta pelin keksimisen jälkeen, yksi löydettiin. Uusien oskillaattorien metsästys kasvoi pelin pääpainopisteeksi, tietotekniikan tulon myötä. Toimiston tietokoneilla tehdyt salaiset etsinnät ovat tulleet pelin kansanperinteen kulmakiviksi. "Yritysten ja yliopistojen keskuskoneilta varastetun tietokoneajan määrä oli huikea", Gosper sanoi.

Koko 1970-luvun matemaatikot ja harrastajat täyttivät muita lyhyitä jaksoja ja löysivät joukon pidempiä. Lopulta matemaatikot löysivät systemaattisen tavan rakentaa pitkän ajanjakson oskillaattorit. Mutta oskillaattorit, joiden jaksot ovat 15–43, osoittautuivat vaikeaksi löytää. "Ihmiset ovat yrittäneet selvittää keskikohtaa vuosia", sanoi Maia Karpovich, jatko-opiskelija Marylandin yliopistosta. Aukkojen täyttäminen pakotti tutkijat haaveilemaan joukosta uusia tekniikoita, jotka ylittivät soluautomaattien mahdolliseksi pidettyjen rajojen, kuten matemaatikot kutsuvat kehittyviä verkkoja, kuten Life.

Nyt Karpovich ja kuusi kirjoittajaa ovat ilmoittaneet a Joulukuun esipainos että he ovat löytäneet kaksi viimeistä puuttuvaa jaksoa: 19 ja 41. Kun nämä aukot on täytetty, elämän tiedetään nyt olevan "kaikkijaksoista" - nimeä positiivinen kokonaisluku, ja on olemassa kuvio, joka toistaa itseään useiden vaiheiden jälkeen.

Elämän tutkimiseen omistautunut kasvava yhteisö, johon kuuluu monia tutkijoita matemaatikoita, mutta myös monia harrastajia, on löytänyt oskillaattorien lisäksi kaikenlaisia ​​uusia malleja. He ovat löytäneet kuvioita, jotka kulkevat ruudukon poikki, nimetty avaruusaluksiksi, ja kuvioita, jotka rakentavat muita kuvioita: aseita, rakentajia ja kasvattajia. He löysivät malleja, jotka laskevat alkulukuja, ja jopa malleja, jotka voivat suorittaa mielivaltaisen monimutkaisia ​​algoritmeja.

Oskillaattorit, joiden jaksot ovat alle 15, voidaan löytää manuaalisesti tai alkeellisilla algoritmeilla, jotka etsivät oskillaattoria solu kerrallaan. Mutta kun ajanjakso pitenee, niin monimutkaisuus kasvaa, mikä tekee raa'an voiman hauista paljon vähemmän tehokkaita. "Pienillä jaksoilla voit etsiä suoraan", sanoi Matthias Merzenich, uuden julkaisun toinen kirjoittaja, joka löysi ensimmäisen periodi-31 oskillaattorin vuonna 2010. "Mutta et voi mennä pidemmälle. Et voi vain valita ajanjaksoa ja etsiä sitä." (Merzenich suoritti matematiikan tohtorin tutkinnon Oregon State Universitystä vuonna 2021, mutta työskentelee tällä hetkellä maatilalla.)

Vuonna 1996 David Buckingham, kanadalainen freelance-tietokonekonsultti ja Life-harrastaja, joka oli etsinyt malleja 1970-luvun lopulta lähtien, osoitti, että oli mahdollista rakentaa ajanjakson 61 ja sitä korkeampia oskillaattorit lähettämällä kuvio suljetun raidan ympäri loputtomassa silmukassa. . Hallitsemalla silmukan pituutta – ja aikaa, joka kaavalle kului yhden edestakaisen matkan tekemiseen – Buckingham huomasi, että hän pystyi tekemään ajanjaksosta niin suuren kuin halusi. "Se on kemiaa ilman hauskoja hajuja tai rikkoutuneita lasitavaroita", hän sanoi. "Kuten yhdisteiden rakentaminen ja niiden välisten vuorovaikutusten tutkiminen." Tämä tarkoitti, että hän oli yhdellä iskulla keksinyt tavan rakentaa mielivaltaisen pitkien ajanjaksojen oskillaattorit, kunhan ne olivat pidempiä kuin 61.

Tuloksia saatiin 1990-luvun puolivälissä, jolloin monet kadonneista oskillaattorista 15–61 löydettiin luovilla yhdistelmillä tunnettuja oskillaattoreita, joille oli annettu värikkäitä nimiä. Pitopalveluja yhdistettiin liikennevaloihin, tulivuoret sylkivät kipinöitä ja syöjät söivät purjelentokoneita.

21-luvun vaihteessa vain kymmenkunta ajanjaksoa oli vielä jäljellä. "Vaikutti hyvin mahdolliselta ratkaista tämä ongelma", Merzenich sanoi. Vuonna 2013 uusi löytö nimeltä Snark-silmukka paransi Buckinghamin vuoden 1996 tekniikkaa ja alensi rajaa, jonka yläpuolella oli helppo rakentaa oskillaattorit, 61:stä 43:een. Tästä jäi vain viisi jaksoa. Yksi löydettiin lisää vuonna 2019 ja kaksi muuta vuonna 2022, jolloin jäljelle jäi vain 19 ja 41 – molemmat huippuluokkaa. "Alkuluvut ovat vaikeampia, koska et voi käyttää pienijaksoisia oskillaattoreita niiden rakentamiseen", Merzenich sanoi.

Mitchell Riley, New Yorkin yliopiston Abu Dhabin tutkijatohtori ja toinen uuden artikkelin toinen kirjoittaja, on pitkään kiehtonut eräänlaista oskillaattoria, jota kutsutaan hassleriksi. "Tapa, jolla hässäkkäät työskentelevät, on, että sinulla on aktiivinen kuvio keskellä ja joitakin vakaata tavaraa ulkopuolella, joka reagoi sen kanssa", Riley selitti. Vakaa aine, jota kutsutaan katalysaattoriksi, on olemassa työntämään aktiivinen kuvio takaisin alkuperäiseen tilaan.

Niiden suunnittelu on vaikeaa. "Kaikki nämä kuviot ovat uskomattoman hauraita", Riley sanoi. "Jos laitat yhden pisteen pois paikalta, ne yleensä vain räjähtävät."

Riley loi Barrister-nimisen ohjelman etsiäkseen uusia katalyyttejä. "Etsimme asetelmia, jotka ovat kestäviä. Koko pointti on, että haluamme heidän olevan vuorovaikutuksessa sen kanssa, mitä keskellä tapahtuu, ja sitten toipuvan", Riley sanoi.

Riley syötti Barristerin löytämiä katalyyttejä toiseen hakuohjelmaan, joka yhdisti ne aktiivisiin kuvioihin. Tämä johti enimmäkseen epäonnistumisiin, hän sanoi. "On melko harvinaista, että yksi näistä katalyyteistä selviää vuorovaikutuksesta. Menestyksestä ei ole takeita. Pidät vain sormet ristissä ja toivot, että saavutat jättipotin. Se tuntuu vähän uhkapelaamiselta."

Lopulta hänen vetonsa kannatti. Muutaman läheltä piti -tilanteen jälkeen – ja koodiin tehdyn muutoksen jälkeen, joka laajensi haun sisältämään symmetriset kuviot – hän löysi katalyyttivuorovaikutuksen, joka voisi ylläpitää 19. periodin oskillaattoria. "Ihmiset olivat yrittäneet kaikenlaisia ​​todella monimutkaisia ​​hakuja, joissa oli paljon katalyyttejä ja paljon harvinaisia ​​aktiivisia asioita keskellä, mutta tarvittiin vain löytää tämä uusi paksu katalyytti", Riley sanoi.

Viimeisen puuttuvan ajanjakson, 41, löysi Nicolo Brown, toinen kirjoittaja, joka on edelleen matematiikan pääaineena Kalifornian yliopistossa Santa Cruzissa. Brown käytti purjelentokoneita katalyytteinä, Merzenichin ensimmäisenä ehdotuksen idean.

"Olemme havainneet niin paljon syvällistä käyttäytymistä viimeisen 10 vuoden aikana", Karpovich sanoi. "Kaikki juhlivat viikon - ja sitten siirtyvät muihin asioihin. On niin monia muita ongelmia ratkaistavaksi." Voidaanko tietyn ajanjakson oskillaattorit pienentää? Löytyykö oskillaattorit, joissa jokainen solu värähtelee? Voiko aseita tehdä tietyillä aikakausilla? Voidaanko avaruusalukset saada kulkemaan tietyllä nopeudella?

Kuten Buckingham sanoi: "On kuin olisi lapsi äärettömässä lelukaupassa."