Matematyczna „gra w życie” ujawnia długo poszukiwane powtarzające się wzorce | Magazyn Quanta

W 1969 roku brytyjski matematyk John Conway opracował urzekająco prosty zestaw reguł tworzenia złożonych zachowań. Jego Gra w Życie, często nazywana po prostu Życiem, toczy się na nieskończonej kwadratowej siatce komórek. Każda komórka może być „żywa” lub „martwa”. Siatka ewoluuje w ciągu serii tur (lub „pokoleń”), a los każdej komórki zależy od ośmiu otaczających ją komórek. Zasady są następujące:

1. Narodziny: Martwa komórka mająca dokładnie trzech żywych sąsiadów staje się żywa.
2. Przetrwanie: Żywa komórka z dwoma lub trzema żywymi sąsiadami pozostaje żywa.
3. Śmierć: żywa komórka mająca mniej niż dwóch lub więcej niż trzech żywych sąsiadów umiera.

Te proste zasady tworzą zdumiewająco różnorodny wachlarz wzorców, czyli „form życia”, które ewoluują z wielu różnych możliwych konfiguracji początkowych siatki. Miłośnicy tej gry podliczyli i usystematyzowali te wzorce w ramach stale rozwijającej się grupy katalog online. Conway odkrył wzór zwany migaczem, który oscyluje pomiędzy dwoma stanami.

W następnym roku odkrył znacznie bardziej skomplikowany wzór zwany pulsarem, który oscyluje pomiędzy trzema różnymi stanami.

Wkrótce po odkryciu oscylatorów pierwsi badacze gry zastanawiali się, czy istnieją oscylatory z każdego okresu. „Na początku widzieliśmy tylko okresy 1, 2, 3, 4 i 15” – powiedział programista i matematyk Bill Gosper, który w ciągu następnych kilku dekad odkrył 17 różnych nowatorskich oscylatorów. Oscylatory z okresu 15 (pokazane poniżej) pojawiały się zaskakująco często w losowych wyszukiwaniach.

Na chętnych czekały niespodzianki. „Z godzin i dni oglądania okres 5 wydawał się niemożliwy” – powiedział Gosper. Następnie w 1971 roku, dwa lata po wynalezieniu gry, znaleziono jedną. Poszukiwanie nowych oscylatorów stało się głównym tematem gry, a zadanie to zostało wzmocnione przez pojawienie się technologii komputerowej. Relacje z tajnych poszukiwań przeprowadzonych na komputerach biurowych stały się kamieniem węgielnym folkloru gry. „Ilość czasu komputerowego skradzionego z komputerów mainframe w firmach i uniwersytetach była zdumiewająca” – powiedział Gosper.

W latach siedemdziesiątych matematycy i hobbyści wypełniali inne krótkie okresy i znajdowali kilka dłuższych. W końcu matematycy odkryli systematyczny sposób budowania oscylatorów długookresowych. Jednak znalezienie oscylatorów z okresami od 1970 do 15 okazało się trudne. „Ludzie od lat próbują znaleźć złoty środek” – powiedział Maja Karpowicz, absolwentka Uniwersytetu Maryland. Wypełnianie luk zmusiło badaczy do wymyślenia mnóstwa nowych technik, które przesunęły granice tego, co uważano za możliwe w przypadku automatów komórkowych, jak matematycy nazywają ewoluujące siatki, takie jak Życie.

Teraz Karpovich i sześciu współautorów ogłosili w: Grudzień preprint że znaleźli dwa ostatnie brakujące okresy: 19 i 41. Po wypełnieniu tych luk wiadomo, że życie jest „omniperiodyczne” — wystarczy podać dodatnią liczbę całkowitą i istnieje wzór, który powtarza się po tylu krokach.

Rozwijająca się społeczność zajmująca się badaniem życia, w skład której wchodzi wielu matematyków zajmujących się badaniami naukowymi, ale także wielu hobbystów, odkryła nie tylko oscylatory, ale także wszelkiego rodzaju nowe wzorce. Znaleźli wzorce przemieszczające się po siatce, zwane statkami kosmicznymi, oraz wzorce tworzące inne wzorce: broń, konstruktorzy i hodowcy. Znaleźli wzorce obliczające liczby pierwsze, a nawet wzorce, które mogą wykonywać dowolnie skomplikowane algorytmy.

Oscylatory z okresami krótszymi niż 15 można znaleźć ręcznie lub za pomocą podstawowych algorytmów, które wyszukują oscylatory po jednej komórce na raz. Jednak w miarę zwiększania się okresu zwiększa się także złożoność, przez co wyszukiwanie metodą brute-force jest znacznie mniej skuteczne. „W przypadku małych okresów można wyszukiwać bezpośrednio” – powiedział Matthias Merzenich, współautor nowego artykułu, który odkrył pierwszy oscylator z okresem 31 w 2010 r. „Ale tak naprawdę nie można wyjść poza to. Nie możesz po prostu wybrać okresu i go wyszukać. (Merzenich uzyskał doktorat z matematyki na Uniwersytecie Stanowym Oregon w 2021 r., ale obecnie pracuje na farmie).

W 1996 roku David Buckingham, kanadyjski niezależny konsultant komputerowy i entuzjasta życia, który poszukiwał wzorców od późnych lat 1970. XX wieku, pokazał, że możliwe jest skonstruowanie oscylatorów o okresie 61 i wyższym, wysyłając wzór po zamkniętej ścieżce w nieskończonej pętli . Kontrolując długość pętli — i czas potrzebny na wykonanie jednego cyklu w obie strony — Buckingham odkrył, że może wydłużyć okres tak długo, jak mu się podoba. „To chemia bez śmiesznych zapachów i potłuczonego szkła” – powiedział. „To jak budowanie związków, a następnie badanie interakcji między nimi”. Oznaczało to, że za jednym zamachem wymyślił sposób konstruowania oscylatorów o dowolnie długich okresach, pod warunkiem, że są one dłuższe niż 61.

W połowie lat 1990. XX wieku uzyskano mnóstwo wyników, kiedy odkryto wiele brakujących oscylatorów od 15 do 61 w wyniku kreatywnych kombinacji znanych oscylatorów, którym nadano mnóstwo kolorowych nazw. Cateringi połączono z sygnalizacją świetlną, wulkany wypluwały iskry, a zjadacze zjadali szybowce.

Na przełomie XXI i XXI wieku zaległych było jeszcze zaledwie kilkanaście okresów. „Wydawało się, że rozwiązanie tego problemu jest bardzo możliwe” – powiedział Merzenich. W 21 roku nowe odkrycie zwane pętlą Snarka udoskonaliło technikę Buckinghama z 2013 roku i obniżyło granicę, powyżej której łatwo było skonstruować oscylatory z 1996 do 61. W rezultacie pozostało tylko pięć brakujących okresów. Jeszcze jedną odkryto w 43 r. i dwie kolejne w 2019 r., pozostawiając jedynie 2022 i 19 – obie pierwsze. „Liczby pierwsze są trudniejsze, ponieważ do ich skonstruowania nie można użyć oscylatorów małookresowych” – powiedział Merzenich.

Mitchell Riley, pracownik naukowy ze stopniem doktora na Uniwersytecie Nowojorskim w Abu Dhabi i inny współautor nowego artykułu, od dawna zaintrygował rodzaj oscylatora zwanego „kłopotem”. „Działanie kłopotów polega na tym, że masz aktywny wzorzec pośrodku i pewne stabilne elementy na zewnątrz, które z nim reagują” – wyjaśnił Riley. Stabilny element, zwany katalizatorem, ma na celu przywrócenie aktywnego wzorca do jego pierwotnego stanu.

Zaprojektowanie ich jest trudne. „Wszystkie te wzorce są niezwykle delikatne” – powiedziała Riley. „Jeśli umieścisz pojedynczą kropkę nie na swoim miejscu, zwykle po prostu eksploduje”.

Riley stworzył program o nazwie Barrister, aby szukać nowych katalizatorów. „Szukamy solidnych martwych natur. Chodzi o to, że chcemy, aby weszli w interakcję z tym, co dzieje się w środku boiska, a następnie odzyskali siły” – powiedział Riley.

Riley wprowadził katalizatory znalezione przez Barristera do innego programu wyszukiwania, który powiązał je z aktywnymi wzorcami. To najczęściej prowadziło do niepowodzeń – dodał. „Dość rzadko zdarza się, aby jeden z tych katalizatorów przetrwał interakcję. Nie ma gwarancji sukcesu. Po prostu trzymaj kciuki i masz nadzieję, że trafisz w dziesiątkę. To trochę przypomina hazard.”

W końcu jego zakład się opłacił. Po kilku niemal błędach — i modyfikacji kodu, która rozszerzyła poszukiwania o wzorce symetryczne — odkrył interakcję z katalizatorem, która mogła podtrzymać oscylator z okresem 19. „Ludzie próbowali wszelkiego rodzaju naprawdę skomplikowanych poszukiwań z dużą ilością katalizatorów i mnóstwem rzadkich substancji aktywnych pośrodku, ale wszystko, co było konieczne, to znalezienie tego nowego, masywnego katalizatora” – powiedział Riley.

Ostatni brakujący okres, 41, odkrył Nicolo Brown, inny współautor, który nadal studiuje matematykę na Uniwersytecie Kalifornijskim w Santa Cruz. Brown użył szybowców jako katalizatorów, pomysł zaproponowany po raz pierwszy przez Merzenicha.

„W ciągu ostatnich 10 lat odkryliśmy wiele głębokich zachowań” – powiedział Karpovich. „Wszyscy świętują przez tydzień, a potem zajmują się innymi sprawami. Jest mnóstwo innych problemów do rozwiązania.” Czy oscylatory danego okresu można zmniejszyć? Czy można znaleźć oscylatory, w których oscyluje każda pojedyncza komórka? Czy można wykonać broń z określonych okresów? Czy statki kosmiczne mogą poruszać się z określoną prędkością?

Jak to ujął Buckingham: „To jak bycie dzieckiem w nieskończonym sklepie z zabawkami”.