A Math „Életjátéka” régóta keresett ismétlődő mintákat tár fel | Quanta Magazin

1969-ben a brit matematikus, John Conway elbűvölően egyszerű szabályrendszert dolgozott ki az összetett viselkedés kialakítására. Életjátéka, amelyet gyakran egyszerűen Életnek neveznek, egy végtelen cellarácson bontakozik ki. Minden sejt lehet „élő” vagy „halott”. A rács egy sor fordulat (vagy „generáció”) során fejlődik, és az egyes cellák sorsát a körülvevő nyolc cella határozza meg. A szabályok a következők:

1. Születés: Egy halott sejt, amelynek pontosan három élő szomszédja van, életre kel.
2. Túlélés: Egy élő sejt két vagy három élő szomszéddal életben marad.
3. Halál: Egy élő sejt, amelynek kettőnél kevesebb vagy háromnál több élő szomszédja van, meghal.

Ezek az egyszerű szabályok elképesztően változatos mintázatokat vagy „életformákat” hoznak létre, amelyek a rács számos lehetséges kiindulási konfigurációjából fejlődnek ki. A játék szerelmesei összeszámolták és taxonomizálták ezeket a mintákat egy folyamatosan bővülőben online katalógus. Conway felfedezte a villogónak nevezett mintát, amely két állapot között oszcillál.

A következő évben talált egy sokkal bonyolultabb mintát, a pulzárt, amely három különböző állapot között ingadozik.

Nem sokkal az oszcillátorok felfedezése után a játék korai felfedezői azon töprengtek, vajon minden korszakban léteznek-e oszcillátorok. „Először csak az 1., 2., 3., 4. és 15. periódusokat láttuk” – mondta Bill Gosper számítógép-programozó és matematikus, aki a következő évtizedekben 17 különböző újszerű oszcillátort fedezett fel. A 15. periódusú oszcillátorok (lásd alább) meglepően gyakran fordultak elő véletlenszerű keresések során.

Meglepetések várták azokat, akik hajlandóak voltak megtalálni őket. "Órák és napok nézése alapján az 5. periódus lehetetlennek tűnt" - mondta Gosper. Aztán 1971-ben, két évvel a játék feltalálása után, találtak egyet. Az új oszcillátorok utáni vadászat a játék fő fókuszpontjává nőtte ki magát, ez a küldetés, amelyet a számítástechnika megjelenése is megerősített. Az irodai számítógépeken végzett titkos keresésekről szóló beszámolók a játék folklórjának sarokkövévé váltak. „Elképesztő volt a vállalati és egyetemi nagyszámítógépektől ellopott számítógépes idő mennyisége” – mondta Gosper.

Az 1970-es években a matematikusok és a hobbibarátok kitöltötték a többi rövid időszakot, és találtak néhány hosszabbat. Végül a matematikusok egy szisztematikus módszert fedeztek fel a hosszú periódusú oszcillátorok felépítésére. De nehéznek bizonyult megtalálni a 15 és 43 közötti periódusú oszcillátorokat. „Az emberek évek óta próbálják kitalálni a közepét” – mondta Maia Karpovich, végzős hallgató a Marylandi Egyetemen. A hiányok pótlása arra kényszerítette a kutatókat, hogy egy csomó új technikát álmodjanak meg, amelyek kitágítják a sejtautomaták által lehetségesnek hitt határokat, ahogy a matematikusok az élethez hasonló fejlődő rácsokat nevezik.

Most Karpovich és hat társszerző bejelentette a Decemberi előnyomás hogy megtalálták az utolsó két hiányzó periódust: a 19-et és a 41-et. Ezekkel a hézagokkal az Élet ma már „minden periódusos”-ként ismert – nevezzen meg egy pozitív egész számot, és létezik egy minta, amely megismétlődik ennyi lépés után.

Az Élet tanulmányozásának szentelt, virágzó közösség, amelyben sok kutató matematikus, de sok hobbi is található, nemcsak oszcillátorokat talált, hanem mindenféle új mintát. Találtak olyan mintákat, amelyek áthaladnak a rácson, amelyeket űrhajóknak neveztek el, és olyan mintákat, amelyek más mintákat építenek: fegyvereket, konstruktőröket és tenyésztőket. Olyan mintákat találtak, amelyek prímszámokat számítanak ki, sőt olyan mintákat is, amelyek tetszőlegesen bonyolult algoritmusokat hajtanak végre.

A 15-nél rövidebb periódusú oszcillátorokat manuálisan vagy olyan kezdetleges algoritmusokkal találhatjuk meg, amelyek cellánként keresik az oszcillátorokat. De ahogy nő az időszak, úgy nő a bonyolultság is, így a nyers erejű keresések sokkal kevésbé hatékonyak. „Kis időszakokra közvetlenül kereshet” – mondta Matthias Merzenich, az új lap társszerzője, aki 31-ben fedezte fel az első periódus-2010-es oszcillátort. „De ezen nem igazán lehet túllépni. Nem választhatsz ki egy időszakot és kereshetsz rá." (Merzenich 2021-ben doktorált matematikából az Oregon Állami Egyetemen, de jelenleg egy farmon dolgozik.)

1996-ban David Buckingham, egy kanadai szabadúszó számítógépes tanácsadó és az élet rajongója, aki az 1970-es évek vége óta keresett mintákat, megmutatta, hogy lehetséges a 61-es és annál magasabb periódusú oszcillátorok konstruálása úgy, hogy egy zárt sáv körül egy végtelen hurokban mintát küldenek. . A hurok hosszának szabályozásával – és a mintának egy oda-vissza út megtételéhez szükséges idő szabályozásával – Buckingham úgy találta, hogy tetszőlegesen hosszúra szabhatja az időszakot. „Ez kémia a vicces szagok és a törött üvegáruk nélkül” – mondta. "Mint például a vegyületek felépítése, majd a köztük lévő kölcsönhatások feltárása." Ez azt jelentette, hogy egy csapásra kitalálta a módját, hogy tetszőlegesen hosszú periódusú oszcillátorokat hozzon létre, amennyiben azok 61-nél hosszabbak.

Az 1990-es évek közepén számos eredmény született, amikor a 15 és 61 közötti hiányzó oszcillátorok közül sokat fedeztek fel ismert oszcillátorok kreatív kombinációi révén, amelyek színes neveket kaptak. A vendéglátókat közlekedési lámpákkal kombinálták, a vulkánok szikrákat köpnek ki, az evők pedig vitorlázókat ettek.

A 21. század fordulóján még csak egy tucat korszak volt kiemelkedő. „Nagyon lehetségesnek tűnt a probléma megoldása” – mondta Merzenich. 2013-ban egy új felfedezés, a Snark hurok javította Buckingham 1996-os technikáját, és 61-ről 43-ra csökkentette azt a határt, amely felett könnyű volt oszcillátorokat építeni. Így már csak öt hiányzó periódus maradt. 2019-ben még egyet, 2022-ben pedig még kettőt fedeztek fel, így csak 19 és 41 maradt – mindkettő kiemelkedő. "A prímszámok nehezebbek, mert nem lehet kis periódusú oszcillátorokat használni a létrehozásukhoz" - mondta Merzenich.

Mitchell Riley-t, a New York-i Egyetem Abu Dhabi posztdoktori kutatóját és az új tanulmány másik társszerzőjét régóta foglalkoztatja az oszcillátor típusa, az úgynevezett hassler. "A szóváltások úgy működnek, hogy van egy aktív minta a közepén, és néhány stabil cucc a kívül, amely reagál rá" - magyarázta Riley. A katalizátornak nevezett stabil anyag azért van, hogy az aktív mintát eredeti állapotába lökje vissza.

Megtervezésük nehéz. „Ezek a minták mindegyike hihetetlenül törékeny” – mondta Riley. "Ha egyetlen pontot is eltesz a helyéről, azok általában felrobbannak."

Riley létrehozta a Barrister nevű programot, hogy új katalizátorokat keressen. „Amit keresünk, az robusztus csendéletek. A lényeg az, hogy azt akarjuk, hogy kapcsolatba lépjenek azzal, ami a közepén történik, majd felépüljenek” – mondta Riley.

Riley katalizátorokat táplált be, amelyeket Barrister talált egy másik keresőprogramba, amely aktív mintákkal párosította őket. Ez többnyire kudarcokhoz vezetett – mondta. „Elég ritka, hogy egy ilyen katalizátor túlélje a kölcsönhatást. Nincs garancia a sikerre. Csak összekulcsolja az ujjait, és reméli, hogy eléri a főnyereményt. Kicsit szerencsejátéknak tűnik.”

Végül a fogadása kifizetődött. Néhány közeli hiba – és a kód olyan módosítása után, amely a keresést szimmetrikus mintákkal is kiterjesztette – talált egy katalizátorkölcsönhatást, amely fenntarthat egy 19. periódusú oszcillátort. "Az emberek mindenféle nagyon bonyolult kereséssel próbálkoztak, sok katalizátorral és sok ritka aktív dologgal a közepén, de csak erre az új, vaskos katalizátorra volt szükség" - mondta Riley.

Az utolsó hiányzó időszakot, 41 évet Nicolo Brown, egy másik társszerző találta meg, aki még mindig a Santa Cruz-i Kaliforniai Egyetem matematika szakos egyetemi hallgatója. Brown vitorlázógépeket használt katalizátorként, ezt az ötletet először Merzenich javasolta.

„Oly sok mély viselkedést fedeztünk fel az elmúlt 10 évben” – mondta Karpovich. „Egy hétig mindenki ünnepel – aztán más dolgokra tér át. Annyi más probléma van még megoldandó.” Egy adott periódusú oszcillátorok kicsinyíthetők? Találhatók-e olyan oszcillátorok, amelyekben minden egyes sejt oszcillál? Készülhetnek-e fegyverek meghatározott időszakokkal? Lehetséges-e az űrhajókat meghatározott sebességgel utazni?

Ahogy Buckingham fogalmazott: „Olyan ez, mint egy gyereknek lenni egy végtelen játékboltban.”