Математична «Гра життя» розкриває довго шукані повторювані шаблони | Журнал Quanta

У 1969 році британський математик Джон Конвей розробив надзвичайно простий набір правил для створення складної поведінки. Його Гра в життя, яку часто називають просто Життям, розгортається на нескінченній квадратній сітці клітин. Кожна клітина може бути «живою» або «мертвою». Сітка розвивається протягом серії поворотів (або «поколінь»), причому доля кожної клітини визначається вісьмома клітинами, які її оточують. Правила такі:

1. Народження: мертва клітина з рівно трьома живими сусідами стає живою.
2. Виживання: жива клітина з двома-трьома живими сусідами залишається живою.
3. Смерть: жива клітина з менш ніж двома або більше ніж трьома живими сусідами гине.

Ці прості правила створюють напрочуд різноманітний набір шаблонів або «форм життя», які розвиваються з багатьох різних можливих початкових конфігурацій сітки. Любителі гри підраховували та класифікували ці шаблони у постійному розширенні Інтернет-каталог. Конвей виявив закономірність під назвою «мигалка», яка коливається між двома станами.

Наступного року він виявив набагато складнішу схему під назвою пульсар, яка коливається між трьома різними станами.

Невдовзі після відкриття осциляторів перші дослідники гри задумалися, чи існують осцилятори кожного періоду. «Спочатку ми бачили лише періоди 1, 2, 3, 4 і 15», — сказав комп’ютерний програміст і математик Білл Госпер, який протягом наступних кількох десятиліть відкрив 17 різних нових осциляторів. Осцилятори періоду 15 (показані нижче) траплялися напрочуд часто під час випадкових пошуків.

Охочих знайти їх чекали сюрпризи. «З огляду на години й дні перегляду період 5 здавався неможливим», — сказав Госпер. Потім у 1971 році, через два роки після того, як гру було винайдено, одну знайшли. Полювання на нові осцилятори перетворилася на головний напрямок гри, пошуки, підкріплені появою комп’ютерних технологій. Розповіді про таємні обшуки, проведені на офісних комп’ютерах, стали наріжним каменем фольклору гри. «Кількість комп’ютерного часу, викраденого з корпоративних та університетських мейнфреймів, була приголомшливою», — сказав Госпер.

Протягом 1970-х років математики та аматори заповнювали інші короткі періоди та знайшли дещицю довших. Згодом математики відкрили систематичний спосіб побудови довгоперіодичних осциляторів. Але осцилятори з періодами від 15 до 43 виявилося важко знайти. «Люди роками намагалися з’ясувати середину», – сказав він Майя Карпович, аспірант Університету Меріленда. Заповнення прогалин змусило дослідників вигадати низку нових методів, які розсунули межі того, що вважалося можливим за допомогою клітинних автоматів, як математики називають розвиваючі сітки, такі як Життя.

Зараз Карпович і шість співавторів оголосили в a Препринт грудня що вони знайшли останні два відсутніх періоди: 19 і 41. Після заповнення цих прогалин життя стало «всеперіодичним» — назвіть додатне ціле число, і існує закономірність, яка повторюється після такої кількості кроків.

Спільнота, що розвивається, присвячена вивченню Життя, до якої входять багато математиків-дослідників, а також багато любителів, знайшла не лише осцилятори, але й різноманітні нові моделі. Вони знайшли шаблони, які подорожують сіткою, які називаються космічними кораблями, і шаблони, які створюють інші шаблони: рушниці, конструктори та заводчики. Вони знайшли шаблони, які обчислюють прості числа, і навіть шаблони, які можуть виконувати як завгодно складні алгоритми.

Осцилятори з періодами, коротшими за 15, можна знайти вручну або за допомогою елементарних алгоритмів, які шукають осцилятори по одній клітинці за раз. Але зі збільшенням періоду зростає і складність, що робить пошук методом грубої сили набагато менш ефективним. «Для невеликих періодів ви можете здійснювати прямий пошук, — сказав Матіас Мерценіх, співавтор нової статті, який відкрив перший осцилятор з періодом 31 у 2010 році. — Але ви не можете вийти далі цього. Ви не можете просто вибрати період і шукати його». (Мерценіх отримав ступінь доктора математики в Університеті штату Орегон у 2021 році, але зараз працює на фермі.)

У 1996 році Девід Бекінгем, канадський незалежний комп’ютерний консультант і ентузіаст Life, який шукав шаблони з кінця 1970-х років, показав, що можна побудувати осцилятори з періодом 61 і вище, посилаючи шаблон навколо замкнутої доріжки в нескінченному циклі. . Контролюючи довжину петлі — і час, потрібний шаблону для завершення однієї подорожі туди й назад — Бекінгем виявив, що він може зробити період настільки великим, як йому заманеться. «Це хімія без смішних запахів і розбитого скляного посуду», — сказав він. «Як будувати сполуки, а потім досліджувати взаємодію між ними». Це означало, що одним махом він винайшов спосіб побудувати осцилятори з як завгодно довгими періодами, якщо вони були довшими за 61.

У середині 1990-х було отримано низку результатів, коли багато зниклих осциляторів від 15 до 61 були виявлені за допомогою творчих комбінацій відомих осциляторів, які отримали ряд яскравих назв. Заклади громадського харчування поєднувалися зі світлофорами, вулкани викидали іскри, а їдці їли планери.

На рубежі 21-го століття лише дюжина періодів залишалася видатною. «Цю проблему здавалося цілком можливим», — сказав Мерценіх. У 2013 році нове відкриття під назвою «петля Снарка» покращило методику Букінгема 1996 року та знизило межу, вище якої можна було легко побудувати осцилятори, з 61 до 43. Це залишило лише п’ять відсутніх періодів. Ще один був виявлений у 2019 році, і ще два у 2022 році, залишивши лише 19 і 41 — обидва першокласні. «Прості числа складніші, тому що ви не можете використовувати осцилятори з малим періодом для їх побудови», — сказав Мерценіх.

Мітчелл Райлі, докторський дослідник Нью-Йоркського університету Абу-Дабі та інший співавтор нової статті, давно заінтригований типом осцилятора, який називається "хеслер". «Спосіб роботи хасслерів полягає в тому, що ви маєте активний шаблон посередині та деякі стабільні речі зовні, які реагують на нього», — пояснив Райлі. Стабільна речовина, яка називається каталізатором, служить для того, щоб повернути активний патерн у вихідний стан.

Спроектувати їх важко. «Усі ці візерунки неймовірно крихкі», — сказав Райлі. «Якщо ви поставите одну крапку не на місці, вона зазвичай просто вибухне».

Райлі створив програму під назвою Barrister для пошуку нових каталізаторів. «Ми шукаємо надійні натюрморти. Вся справа в тому, що ми хочемо, щоб вони взаємодіяли з тим, що відбувається в середині, а потім відновилися», — сказав Райлі.

Райлі подав каталізатори, знайдені Баррістером, в іншу пошукову програму, яка поєднала їх з активними шаблонами. За його словами, це здебільшого призвело до невдач. «Досить рідко один із цих каталізаторів виживає після взаємодії. Немає гарантії успіху. Ви просто схрещуєте пальці і сподіваєтесь, що виграєте джекпот. Це трохи схоже на азартну гру».

Зрештою його ставка виправдалася. Після кількох невдалих помилок — і модифікації коду, яка розширила пошук, включивши симетричні шаблони — він знайшов взаємодію каталізатора, яка могла підтримувати осцилятор з періодом 19. «Люди випробовували всілякі справді складні пошуки з великою кількістю каталізаторів і великою кількістю рідкісних активних речей посередині, але все, що потрібно, — це знайти цей новий масивний каталізатор», — сказав Райлі.

Останній пропущений період, 41, був знайдений Ніколо Брауном, ще одним співавтором, який все ще вивчає математику в Каліфорнійському університеті в Санта-Крус. Браун використовував планери як каталізатори, ідея, яку вперше запропонував Мерценіх.

«За останні 10 років ми виявили стільки глибокої поведінки», — сказав Карпович. «Усі святкують протягом тижня, а потім переходять до інших справ. Є так багато інших проблем, які потрібно вирішити». Чи можна зробити осцилятори заданого періоду меншими? Чи можна знайти осцилятори, у яких кожна окрема клітина коливається? Чи можна виготовляти зброю з певними періодами? Чи можна змусити космічні кораблі рухатися з певною швидкістю?

Як сказав Бекінгем: «Це як дитина в нескінченному магазині іграшок».