Conway's Game of Life is Omniperiodic. Nico Brown,...

Conway's Game of Life is Omniperiodic
Nico Brown, Carson Cheng, Tanner Jacobi, Maia Karpovich, Matthias Merzenich, David Raucci, Mitchell Riley
Статья: https://arxiv.org/abs/2312.02799

Прекрасное субботнее!

Доказано, что игра Жизнь омнипериодическая (omniperiodic), то есть в ней есть конструкции с любым периодом.

Напомню, что игра Жизнь (The Game of Life) -- это клеточный автомат, предложенный британцем Джоном Конуэем в 1970-м. У нас тут было сколько-то постов про Жизнь (https://t.me/gonzo_ML/1817), Конуэя (https://t.me/gonzo_ML/1825), и всё такое (https://t.me/gonzo_ML/1042), в нашем чате были также обсуждения развития игры, например, Lenia (https://t.me/c/1334131803/12841, https://t.me/c/1334131803/14282). Но сегодня про классическую классику.

В игре клетки живут на двумерной плоскости с квадратной сеткой, и у каждой клетки 8 соседей. Клетка может быть либо живая (закрашенная), либо мёртвая (пустая). Игра пошаговая, в каждый дискретный момент времени всё поле изменяется в соответствии с двумя правилами:
* Если вокруг мёртвой клетки ровно три живых соседа, то она становится живой.
* Если вокруг живой клетки два или три живых соседа, то она остаётся живой.
* В остальных случаях живая клетка умирает.

Период -- это время, через которое конфигурация клеток в игре повторяется. Сама такая конфигурация называется осциллятором.

Уже в самом начале были найдены простенькие (да и простые тоже) осцилляторы, типа квадратного блока 2x2 (p1), мигалки (p2), пульсара (p3) или глайдера (который не совсем осциллятор, он ещё и в пространстве перемещается, поэтому он космический корабль, spaceship). Многие из них получаются сами из рандомной начальной конфигурации.

При этом долго существовала гипотеза, что в Жизни должны существовать осцилляторы любого периода >=1. Важно, что тут речь про конечные осцилляторы, потому что с бесконечными всё просто -- сделал цепочку глайдеров на нужном расстоянии и усё.

Осцилляторы периода <=15 были найдены вручную. В 1996 David Buckingham показал, что можно создать любой осциллятор периода >=61 с помощью трубопроводов Гершеля (Herschel conduits), где сигнал пересылается по замкнутому пути (пример). Затем этот порог снизили до 43, обнаружив Снарка (Snark), отражатель глайдеров под углом в 90 градусов.

Оставалась неясная часть с 15 < p < 43, особенно сложно было с простыми числами. В начале тысячелетия недоставало осцилляторов периодов 19, 23, 27, 31, 34, 37, 38, 39, 41, 43, 51 и 53. Последними держались периоды 19 (https://conwaylife.com/wiki/Cribbage) и 41 (https://conwaylife.com/wiki/204P41). Но теперь найдены и они, и Жизнь доказанно омнипериодическая. Откроем шампанское!

Дальше советую занырнуть в статью, там во второй главе прекрасное историческое описание поисков, которое надо читать as is, а не пересказывать. Также в статье кликабельные картинки всех осцилляторов, ведущие на интерактивную демонстрацию, с которой можно поиграть. Мы с детьми теперь там сидим.

Тема с периодами теперь закрыта, но открыты другие интересные темы. Например, про максимальную скорость космических кораблей. Мне кажется, у Конрада Цузе в его Rechnender Raum (https://philpapers.org/archive/ZUSRR.pdf) тоже про что-то такое было, но давно читал, надо пересмотреть. В любом случае привет Теории Относительности :)

Также ещё не найдены глайдерные пушки всех периодов. Желающие могут поискать периоды 14 ≤ p ≤ 19, и p = 23, 26, 29, 31, 35, 38, 39, 47, 53. Есть и другие интересные темы, например, про оптимизацию осцилляторов (собрать минимальную по количеству клеток конфигурацию) или про strictly volatile осцилляторы, у которых каждая клетка пульсирует с заданным периодом. Интересно, кстати, что для поисков используются SAT-солверы, но это недоисследованная тема.

В общем круть даже в классике. И ждём также развития темы про клеточные автоматы, в частности были упомянутые по ссылкам выше многообещающие заходы на нейронные клеточные автоматы (https://distill.pub/2020/growing-ca/) от нашего любимого Майкла Левина.

Всем хороших выходных!