„Jocul vieții” de la matematică dezvăluie modele repetate mult căutate | Revista Quanta

În 1969, matematicianul britanic John Conway a conceput un set de reguli ademenitor de simplu pentru crearea unui comportament complex. Jocul său al vieții, denumit adesea pur și simplu Viață, se desfășoară pe o rețea pătrată infinită de celule. Fiecare celulă poate fi fie „vie”, fie „moartă”. Grila evoluează pe o serie de ture (sau „generații”), soarta fiecărei celule fiind determinată de cele opt celule care o înconjoară. Regulile sunt următoarele:

1. Naștere: O celulă moartă cu exact trei vecini vii devine vie.
2. Supraviețuire: O celulă vie cu doi sau trei vecini vii rămâne în viață.
3. Moarte: o celulă vie cu mai puțin de doi sau mai mult de trei vecini vii moare.

Aceste reguli simple creează o gamă uimitor de diversă de modele, sau „forme de viață”, care evoluează din numeroasele configurații de pornire posibile ale rețelei. Iubitorii de joc au numărat și taxonomizat aceste modele într-o continuă expansiune catalog online. Conway a descoperit un model numit intermitent, care oscilează între două stări.

În anul următor, el a găsit un model mult mai complicat numit pulsar, care oscilează între trei stări diferite.

La scurt timp după descoperirea oscilatorilor, primii exploratori ai jocului s-au întrebat dacă există oscilatori pentru fiecare perioadă. „La început, am văzut doar perioadele 1, 2, 3, 4 și 15”, a spus programatorul și matematicianul Bill Gosper, care va descoperi 17 noi oscilatori diferite în următoarele decenii. Oscilatorii din perioada 15 (prezentați mai jos) au apărut surprinzător de des în căutări aleatorii.

Surprizele au pândit pentru cei dispuși să le găsească. „Din ore și zile de vizionare, perioada 5 părea imposibilă”, a spus Gosper. Apoi, în 1971, la doi ani după ce jocul a fost inventat, a fost găsit unul. Căutarea de noi oscilatoare a devenit un obiectiv major al jocului, o căutare susținută de apariția tehnologiei computerizate. Conturile de căutări ascunse efectuate pe computerele de birou au devenit o piatră de temelie a folclorului jocului. „Cantitatea de timp pe calculator furată de la sistemele centrale corporative și universitare a fost uluitoare”, a spus Gosper.

De-a lungul anilor 1970, matematicienii și pasionații au completat celelalte perioade scurte și au găsit o serie de altele mai lungi. În cele din urmă, matematicienii au descoperit o modalitate sistematică de a construi oscilatoare cu perioadă lungă. Dar oscilatorii cu perioade între 15 și 43 s-au dovedit greu de găsit. „Oamenii au încercat să-și dea seama de mijloc de ani de zile”, a spus Maia Karpovici, student absolvent la Universitatea din Maryland. Completarea golurilor i-a forțat pe cercetători să viseze o serie de tehnici noi care au împins limitele a ceea ce se credea posibil cu automatele celulare, așa cum matematicienii numesc grile în evoluție precum Viața.

Acum Karpovich și șase coautori au anunțat într-o Pretipărire decembrie că au găsit ultimele două perioade lipsă: 19 și 41. Cu acele goluri umplute, se știe că Viața este acum „omniperiodică” – numiți un număr întreg pozitiv și există un model care se repetă după atât de mulți pași.

Comunitatea în plină dezvoltare dedicată studierii Vieții, care include mulți matematicieni de cercetare, dar și mulți pasionați, a găsit nu numai oscilatori, ci și tot felul de noi modele. Ei au găsit modele care călătoresc prin grilă, denumite nave spațiale și modele care construiesc alte modele: arme, constructori și crescători. Ei au găsit modele care calculează numere prime și chiar modele care pot executa algoritmi arbitrar complicati.

Oscilatorii cu perioade mai scurte de 15 pot fi găsite manual sau cu algoritmi rudimentari care caută oscilatori câte o celulă. Dar, pe măsură ce perioada devine mai mare, crește și complexitatea, făcând căutările prin forță brută să fie mult mai puțin eficiente. „Pentru perioade mici, puteți căuta direct”, a spus Matthias Merzenich, un coautor al noii lucrări, care a descoperit primul oscilator perioada 31 în 2010. „Dar nu puteți depăși cu adevărat asta. Nu poți să alegi o perioadă și să o cauți.” (Merzenich și-a obținut doctoratul în matematică la Universitatea de Stat din Oregon în 2021, dar în prezent lucrează la o fermă.)

În 1996, David Buckingham, un consultant canadian independent de calculatoare și pasionat de viață, care a căutat modele de la sfârșitul anilor 1970, a arătat că este posibil să se construiască oscilatoare din perioada 61 și mai mare prin trimiterea unui model în jurul unei piste închise într-o buclă nesfârșită. . Controlând lungimea buclei - și timpul necesar modelului pentru a finaliza o călătorie dus-întors - Buckingham a constatat că ar putea face perioada cât de mare dorea. „Este chimie fără mirosuri amuzante sau sticlă spartă”, a spus el. „Precum construirea de compuși și apoi explorarea interacțiunilor dintre ele.” Aceasta însemna că, dintr-o singură lovitură, a venit cu o modalitate de a construi oscilatoare cu perioade arbitrar de lungi, atâta timp cât acestea erau mai mari de 61.

Au existat o mulțime de rezultate la mijlocul anilor 1990, când mulți dintre oscilatorii lipsă între 15 și 61 au fost descoperiți prin combinații creative de oscilatoare cunoscute, cărora li s-au dat o serie de nume colorate. Cateringurile erau combinate cu semafoare, vulcanii scuipau scântei, iar mâncătorii mâncau planoare.

Până la începutul secolului al XXI-lea, doar o duzină de perioade erau încă restante. „Părea foarte posibil să se rezolve această problemă”, a spus Merzenich. În 21, o nouă descoperire numită bucla Snark a îmbunătățit tehnica lui Buckingham din 2013 și a scăzut pragul peste care era ușor să construiești oscilatoare de la 1996 la 61. Aceasta a lăsat doar cinci perioade lipsă. Încă unul a fost descoperit în 43 și încă două în 2019, lăsând doar 2022 și 19 - ambele prime. „Primele sunt mai grele pentru că nu puteți folosi oscilatoare cu perioade mici pentru a le construi”, a spus Merzenich.

Mitchell Riley, cercetător postdoctoral la Universitatea din New York Abu Dhabi și un alt coautor al noii lucrări, a fost mult timp intrigat de un tip de oscilator numit hassler. „Modul în care lucrează hasslers este că ai un model activ în mijloc și niște lucruri stabile în exterior care reacționează cu el”, a explicat Riley. Materialul stabil, numit catalizator, este acolo pentru a împinge modelul activ înapoi în starea sa originală.

Proiectarea lor este dificilă. „Toate aceste modele sunt incredibil de fragile”, a spus Riley. „Dacă puneți un singur punct din loc, de obicei, pur și simplu explodează.”

Riley a creat un program numit Barrister pentru a căuta noi catalizatori. „Ceea ce căutăm sunt naturi moarte care sunt robuste. Ideea este că vrem ca ei să interacționeze cu ceea ce se întâmplă la mijloc și apoi să-și revină”, a spus Riley.

Riley a alimentat catalizatori pe care Barrister i-a găsit într-un alt program de căutare care le-a asociat cu modele active. Acest lucru a dus în mare parte la eșecuri, a spus el. „Este destul de rar ca unul dintre acești catalizatori să supraviețuiască interacțiunii. Nu există nicio garanție de succes. Îți cam încrucișezi degetele și speri că ai câștigat jackpot-ul. Se simte un pic ca la jocuri de noroc.”

În cele din urmă, pariul lui a dat roade. După câteva erori aproape - și o modificare a codului care a extins căutarea pentru a include modele simetrice - el a găsit o interacțiune catalizatoare care ar putea susține un oscilator din perioada 19. „Oamenii au încercat tot felul de căutări cu adevărat complicate, cu o mulțime de catalizatori și o mulțime de lucruri active rare în mijloc, dar tot ce era necesar era să găsească acest nou catalizator gros”, a spus Riley.

Ultima perioadă lipsă, 41 de ani, a fost găsită de Nicolo Brown, un alt coautor, care este încă licență în matematică la Universitatea din California, Santa Cruz. Brown a folosit planoare ca catalizatori, idee propusă pentru prima dată de Merzenich.

„Am descoperit atât de mult comportament profund în ultimii 10 ani”, a spus Karpovich. „Toată lumea sărbătorește o săptămână – și apoi trece la alte lucruri. Sunt atât de multe alte probleme de rezolvat.” Pot fi micșorate oscilatorii unei perioade date? Pot fi găsite oscilatoare în care fiecare celulă oscilează? Se pot produce arme cu anumite perioade? Navele spațiale pot fi făcute să călătorească cu anumite viteze?

După cum a spus Buckingham, „Este ca și cum ai fi un copil într-un magazin infinit de jucării”.