Математическая загадка «Игры В Жизнь», над которой бились десятилетиями, наконец разгадана

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

Закономерность в игре «Жизнь», которая повторяется каждые 19 шагов

Давняя загадка о повторяющихся узорах в двумерной математической игре была разгадана спустя более 50 лет после того, как были найдены два последних элемента головоломки.

Считается, что результат не имеет никакого практического применения, но удовлетворит любопытство группы энтузиастов, одержимых игрой «Жизнь».

Игра «Жизнь», придуманная математиком Джоном Конвеем в 1970 году, представляет собой клеточный автомат — упрощённую модель мира, состоящую из сетки «живых» и «мёртвых» клеток. Игроки создают начальный паттерн, который обновляется поколение за поколением в соответствии с простыми правилами.

Живая клетка, у которой менее двух соседних живых клеток, в следующем поколении становится мёртвой; живая клетка, у которой две или три соседние живые клетки, остаётся живой; а живая клетка, у которой более трёх соседних живых клеток, погибает. Мёртвая клетка, у которой ровно три соседние живые клетки, в следующем поколении становится живой. В противном случае она остаётся мёртвой.

Эти правила создают развивающиеся паттерны, кажущиеся бесконечно сложными, которые образуют три типа фигур: статичные объекты, которые не меняются; «осцилляторы», которые образуют повторяющийся, но неподвижный паттерн; и «космические корабли», которые повторяются, но при этом перемещаются по сетке.

Одна из нерешённых проблем в исследовании «Жизни» заключается в том, существуют ли осцилляторы с любым «периодом»: повторяющиеся каждые два шага, каждые три шага и так далее до бесконечности. Была веская причина полагать, что это так, когда математик Дэвид Бакингем разработал метод, позволяющий создавать осцилляторы с любым периодом выше 57, но для некоторых меньших чисел осцилляторы всё ещё не были найдены.

Теперь группа энтузиастов заполнила последние пробелы, опубликовав статью, в которой описываются осцилляторы с периодами 19 и 41 — последние недостающие формы.

Один из членов команды, Митчелл Райли из Нью-Йоркского университета в Абу-Даби, занимается этой проблемой в качестве хобби параллельно с исследованиями в группе квантовых вычислений. Он говорит, что существует множество методов создания новых осцилляторов, но не найдено способа создавать их с определёнными периодами, а это значит, что исследования в этой области — игра случая. «Это как играть в дартс — мы просто никогда не попадали в 19 и 41», — говорит он.

Райли просматривал списки известных форм, состоящих из двух частей: хасслера и катализатора. Любители «Жизни» придумали эти термины для обозначения статичных форм — катализаторов, — внутри которых находится изменяющаяся форма — хасслер. Внутренняя часть реагирует на внешнюю, но не меняет её, и вместе они образуют осциллятор с определённым периодом. Райли написал компьютерную программу для поиска потенциально полезных катализаторов.

«Нужно, чтобы звёзды сошлись, — говорит он. — Нужно, чтобы реакция внутри не разрушила то, что снаружи, и чтобы реакция внутри случайно вернулась в исходное состояние в один из этих новых периодов».

Райли говорит, что у этого исследования нет практического применения и что он занялся этой проблемой «из чистого любопытства».

Сьюзан Степни из Йоркского университета, Великобритания, говорит, что работа демонстрирует некоторые “чрезвычайно умные и креативные приемы”, но это, конечно, не окончательный вывод исследования творения Конвея.

«Я не думаю, что работа над „Игрой жизни“ когда-нибудь будет завершена, — говорит Степни. — Система универсальна с точки зрения вычислений, поэтому всегда можно найти новые варианты поведения. Она кажется такой простой в описании, но настолько сложна в поведении, что продолжает восхищать многих».