«Игра жизни» математики раскрывает долгожданные повторяющиеся закономерности | Журнал Кванта

В 1969 году британский математик Джон Конвей разработал удивительно простой набор правил для создания сложного поведения. Его Игра Жизни, которую часто называют просто Жизнью, разворачивается на бесконечной квадратной сетке ячеек. Каждая клетка может быть либо «живой», либо «мертвой». Сетка развивается в течение серии ходов (или «поколений»), при этом судьба каждой ячейки определяется восемью окружающими ее ячейками. Правила следующие:

1. Рождение: Мертвая клетка, имеющая ровно три живых соседа, становится живой.
2. Выживание: Живая клетка с двумя или тремя живыми соседями остается живой.
3. Смерть: Живая клетка, имеющая менее двух или более трех живых соседей, умирает.

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

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

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

Тех, кто хотел их найти, ждали сюрпризы. «Судя по часам и дням просмотра, пятый период казался невозможным», — сказал Госпер. Затем в 5 году, через два года после изобретения игры, она была найдена. Охота за новыми генераторами стала основным направлением игры, и этот квест подкрепился появлением компьютерных технологий. Отчеты о тайных обысках, проведенных на офисных компьютерах, стали краеугольным камнем игрового фольклора. «Количество компьютерного времени, украденного с корпоративных и университетских мэйнфреймов, ошеломляет», — сказал Госпер.

На протяжении 1970-х годов математики и любители заполняли другие короткие периоды и обнаружили несколько более длинных. В конце концов математики открыли систематический способ создания долгопериодических осцилляторов. Но найти осцилляторы с периодами от 15 до 43 оказалось непросто. «Люди годами пытались найти середину», — сказал он. Майя Карпович, аспирант Университета Мэриленда. Заполнение пробелов заставило исследователей придумать множество новых методов, которые раздвинули границы того, что считалось возможным с помощью клеточных автоматов, как математики называют развивающиеся сетки, такие как Жизнь.

Теперь Карпович и шесть соавторов объявили в декабрьский препринт что они нашли два последних недостающих периода: 19 и 41. Теперь, когда эти пробелы заполнены, Жизнь стала «всепериодической» — назовите положительное целое число, и существует закономерность, которая повторяется после такого количества шагов.

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

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

В 1996 году Дэвид Бакингем, канадский компьютерный консультант-фрилансер и энтузиаст жизни, который искал закономерности с конца 1970-х годов, показал, что можно построить осцилляторы с периодом 61 и выше, отправляя модель по замкнутой дорожке в бесконечном цикле. . Контролируя длину цикла — и время, необходимое шаблону для совершения одного обхода туда и обратно, — Бэкингем обнаружил, что может сделать период настолько большим, насколько пожелает. «Это химия без странных запахов и битой посуды», — сказал он. «Например, создавать соединения, а затем исследовать взаимодействия между ними». Это означало, что он одним махом нашел способ создавать осцилляторы с произвольно длинными периодами, если они длиннее 61.

В середине 1990-х годов было получено множество результатов, когда многие из недостающих осцилляторов между 15 и 61 были обнаружены посредством творческих комбинаций известных осцилляторов, которым было присвоено множество красочных названий. Поставщики общественного питания были объединены со светофорами, вулканы выплевывали искры, а едоки ели планеры.

К началу XXI века оставалось невыполненным лишь дюжина периодов. «Казалось, решить эту проблему вполне возможно», — сказал Мерцених. В 21 году было сделано новое открытие под названием «петля Снарка», усовершенствовавшее метод Букингема 2013 года и понизившее пороговое значение, выше которого было легко построить осцилляторы, с 1996 до 61. В результате осталось только пять пропущенных периодов. Еще один был обнаружен в 43 году, а еще два — в 2019 году, остались только 2022 и 19 — оба простые. «Простые числа сложнее, потому что для их построения нельзя использовать осцилляторы с малым периодом», — сказал Мерцених.

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

Проектировать их сложно. «Все эти модели невероятно хрупкие», — сказал Райли. «Если вы поставите одну точку не на своем месте, они обычно просто взорвутся».

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

Райли загрузил катализаторы, найденные Барристером, в другую поисковую программу, которая соединила их с активными шаблонами. По его словам, это в основном приводило к неудачам. «Достаточно редко один из этих катализаторов переживает взаимодействие. Нет никакой гарантии успеха. Вы просто скрещиваете пальцы и надеетесь, что сорвали джекпот. Это немного похоже на азартную игру».

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

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

«За последние 10 лет мы обнаружили так много глубокого поведения», — сказал Карпович. «Все празднуют неделю, а потом переходят к другим делам. Есть так много других проблем, которые нужно решить». Можно ли сделать осцилляторы данного периода меньше? Можно ли найти осцилляторы, в которых колеблется каждая клетка? Можно ли изготавливать оружие с определенными периодами? Можно ли заставить космические корабли двигаться с определенной скоростью?

Как выразился Бэкингем: «Это как быть ребенком в бесконечном магазине игрушек».