Игра «Жизнь» — как собрать произвольный шаблон всего из 15 глайдеров

В сообществе игры «Жизнь», изобретённой Джоном Конвеем, отмечали знаковое достижение, совершённое 9 ноября 2022 года. Идея, на воплощение которой ушли годы – проект «обратный шестометатель» — наконец дошла до той стадии, когда в наличии имелись все компоненты для этой сущности, позволявшие достичь заявленной цели.  

Цель проста. Выбираем любой шаблон, который можно собрать в «Жизни» - например, Тихоходку. Начинаем с небольшого количества шаблонов (пока 15), так, чтобы в пустой вселенной для «Game of Life» присутствовали только они. С течением времени из этих глайдеров должен собраться данный шаблон. Никакого остаточного мусора, разбросанной основы – только чистый синтез того, что вы выберете. Данный пост рассказывает, как устроен этот механизм, как мы до него дошли, и почему это так круто.

Как такое вообще возможно?

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

При наличии 15 глайдеров (или любого другого фиксированного количества) вся разница между одним и другим первичным множеством заключается в том, где они начинаются. Поскольку можно создать бесконечное количество разных шаблонов, необходимо составить список из бесконечного числа вариантов упорядочивания 15 глайдеров. Это возможно, но, только если воспользоваться соответственно неограниченным расстоянием как минимум в одной паре глайдеров в данном рецепте.

С таким ограничением затепливается надежда. Тот факт, что нам потребуется огромное расстояние, наводит нас на первый принцип. В расстоянии как таковом кодируется информация.

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

Сомнительные начинания

Вначале был Густаво, бразильский энтузиаст конвеевской игры «Жизнь», имевший привычку сильно отклоняться от темы на форумах. В новом треде Густаво стал рассуждать об утечке секретного сигнала из MIT – сигнал был на коде Морзе, и Густаво якобы занимался его расшифровкой. Казалось, что тема сообщения – «Игра Жизнь – Исследование синтеза космических кораблей». Сообщество взялось за разбор этого треда самым уморительным образом. Некоторые пытались подшучивать над Густаво, требовали доказательств или стремились выпятить неувязки, имевшиеся в его истории.

Вся эта история представляла собой воображаемый нонсенс без всякой сути. Пользователь gameoflifeboy сказал, что это «самый пальнутый тред на форуме за весь 2015 год». Но одна часть дискуссии выделялась. Густаво утверждал, что, занимаясь своим перехватом, он узнал, что можно синтезировать огромный ранее не известный космический корабль – больше Гусеницы, собираемый из 386 глайдеров.

Адам Гуше, небезызвестный математик и автор блога cp4space счёл этот тезис правдоподобным. Не по происхождению, поскольку вся эта история была всего лишь плодом фантазии одного интернет-тролля. Правдоподобным ему показалось то, что сверхсложный шаблон можно синтезировать из относительно небольшого числа глайдеров. Процитируем его:   

Поскольку можно синтезировать универсальный конструктор из 385, весь чертёж можно закодировать в «расстоянии» между конечным глайдером и конструктором (программируя по Гёделю или как-то иначе).

Адам Гуше

Универсальные конструкторы

Универсальные конструкторы также фигурируют в моём посте о тихоходках. На этот раз я постараюсь разобрать данную тему чуть подробнее, проведя аналогию с машинами Тьюринга.

Часто приходится слышать, что машина Тьюринга не уступает по мощности современному компьютеру, так как на ней можно выполнять все те же алгоритмы (хотя, возможно, не так быстро). Аналогично, есть мнение, что гораздо более слабые системы, например, Rule 110, столь же мощны, как и машина Тьюринга. Не будучи ни лучшим, ни худшим по эффективности образцом компьютера, машина Тьюринга канонически считается отсчётным уровнем для оценки вычислительной мощности. Любая система с эквивалентными вычислительными возможностями считается «Тьюринг-полной».

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

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

Пример

Я собираюсь повторно воспользоваться примером, приведённым в статье о Тихоходках, поэтому здесь продемонстрирую, как собрать универсальную конструкцию, просто тщательно соблюдая дистанцию между глайдерами, расположенными вдоль единой разделяемой дорожки. Досмотрите до конца, я покажу, как собирать элементы, расположенные далеко-далеко от этой дорожки.

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

Чтобы это доказать, требовалось выработать процесс, позволявший бы конвертировать рецепт из одной системы в другую. Данная редукция выглядела так:

• Строим синхронизированные глайдеры, поступающие отовсюду, для этого создаём «зародышевую совокупность» - это просто куча объектов, превращающихся в глайдеры, как только до них докатывается реакция.

• Строим «зародышевую совокупность», отправляя глайдеры к цели один за другим (когда глайдеры не синхронизированы, такой феномен называется «последовательный залп»).

Это так, впечатление о жаргоне составить. Но, в принципе, всё логично. Зародышевые совокупности не уступают по силе столкновениям глайдеров. Зародышевые совокупности можно создавать при помощи последовательных залпов, поэтому и они не уступают по мощности столкновениям глайдеров. А строительные стремянки, в том числе, имеющая нулевой угол из предыдущего видео, просто по-своему позволяют давать последовательные залпы, так что эквивалентность продолжается и на этом уровне.

Шорткаты

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

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

А ещё однажды удалось построить:

Возвращаясь к теме

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

Уикендер. Специфическая коллекция из 33 глайдеров, которую я показал при сборке уикендера. Коллекция из тысяч глайдеров, аккуратно расположенных вдоль одной дорожки, с построением отражателя. Десятичный счётчик или зародышевая совокупность для него.

И, наконец, финальное достижение – проект по постройке обратного шестометателя (RCT) – показывает, что все эти вещи можно аккуратно собрать, воспользовавшись первичным набором всего из 15 глайдеров.

Универсальный конструктор

Было бы слегка парадоксально рассматривать «синтез» любого из актуальных примеров на основе универсальных конструкторов. Ведь в этих системах заложены рецепты для Конкретной Конструируемой Штуки – будь то в разнесении или в положении неограниченного количества объектов, зачастую – глайдеров. Можно упрощённо предположить, что тогда в каждом экземпляре конструкции содержится разное количество глайдеров, что противоречит нашей цели.

Или нет?

Эка невидаль – использовать некоторое небольшое количество глайдеров, чтобы создать гораздо большее множество. Можно привести довольно тривиальный пример: на сборку глайдерного ружья Госпера требуется 8 глайдеров, а на разрушение – 2. Если дать ему поработать до разрушения немного дольше, то будет создано ещё больше глайдеров. Но глайдеры, выстреливаемые из такого ружья, отличаются сильной регулярностью, поэтому с их помощью не закодировать никакой новаторский вариант конструкции, как долго бы ружьё ни служило.

А что, если?

А что, если рассмотреть проект, в котором как-нибудь собирались бы и разрушались любые возможные сущности, до тех пор, пока не поступит прерывание с требованием остановиться на актуальной штуке? Красивый мысленный эксперимент, но он быстро обрастает проблемами. Сложно разрушить вещь, не зная, что она собой представляет. Более того, в состав некоторых вещей входят космические корабли, которые начинают разлетаться на большой скорости. Ничто из того, что вы могли бы построить, их не догонит и не разрушит.

Нет, оказалось, что просто нужен способ многократно считывать информацию об «очень далёком» материале, так, чтобы при каждом считывании приобреталась новая информация. Единственного считывания ни в коем случае не хватит.

Шестометатель

Ещё в 1991 году Дин Хикерсон собрал шаблон, в котором глайдер скакал туда-сюда между стационарным объектом и отдалённым космическим кораблём. Всякий раз длина пролёта удваивалась. Подобный подход используется в созданной недавно тетрационной машине, но старая конструкция Хикерсона конструировалась ради красоты, а не деоптимизировалась для тормознутости.

Чтобы было понятнее, почему путь удваивается, давайте поупражняемся в математике пространства-времени. Глайдер перемещается по диагонали на 1 плитку каждые 4 тика. Далёкий космический корабль, «корабль Кордера», перемещается по диагонали на 8 плиток за 96 тиков или, в среднем, со скоростью 1 в 12. Если исходное расстояние между глайдером и кораблём равно D, то глайдеру, чтобы догнать космический корабль, требуется D / (1/4 – 1/12) или 6D поколений. Затем глайдер разворачивается и покрывает то же расстояние (чтобы вернуться в точку старта) ещё за 6D поколений. Всего истекает 12D поколений, за это время корабль Кордера успевает продвинуться на D плиток дальше – имеем чистое удваивание.

Если стационарный объект сконфигурирован на совершение некоторого действия всякий раз, когда от него отражается глайдер, имеем такой результат, как показан ниже.

Здесь, при оценке ситуации в таких масштабах, начинает просматриваться проблема. Каждый следующий отправленный глайдер тратит на дорогу вдвое больше времени, чем предыдущий. Популяция растёт по логарифмической шкале, что само по себе круто.

И наоборот

Теперь рассмотрим, что произойдёт, если корабль Кордера станет не отдаляться от машины, а приближаться к ней. Он всё равно успеет многократно отзеркалить сигнал туда-сюда.

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

Но здесь есть предел. В конце концов корабль Кордера прибывает, и вся конструкция превращается в лепёшку.

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

Побитовое считывание

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

Если обозначить через 1 тот глайдер, который нужно округлять, а через 0 – тот, который не нужно округлять, то исходная позиция корабля Кордера может быть представлена в виде списка единиц и нулей. Конечный список из единиц и нулей – это потенциальный рецепт. Вот и тот способ закодировать информацию через расстояние, который мы надеялись отыскать. Причём, тут кодируется не просто информация, а дискретные биты, каждый из которых считывается по отдельности.

Это и есть Обратный Шестометатель, он же RCT. Так называется любая система, сигнал в которой отражается туда-сюда с уполовиниванием расстоянии на каждом шаге. Считывание чётности на каждом шаге даёт новый бит информации.

Непричёсанные тонкости

Итак, всё, что от нас требовалось – это

• Изыскать, как заставить эти нули и единицы функционировать в качестве универсального конструктора.

• Найти простейший глайдерный рецепт для создания системы, обладающей свойствами обратного шестометателя

• На основе нулей и единиц написать рецепт, который бы не только обеспечивал конструирование конкретной вещи, но и подчищал весь беспорядок, остающийся на месте RCT

Вероятно, вы уже догадываетесь, что ни одна из этих задач не далась просто. В большинстве случаев сообщество уделяло внимание только первым двум пунктам из списка, а третий пускало на самотёк как теоретически неизбежный. Поэтому большинство исходных проектов получались неполными, и Нужная Штука никак не получалась. Но сообщество всё равно вело счёт глайдерам.

Неполный проект #1: 329 глайдеров

Дэйв Грин и Адам Гуше первыми пометили пункт #1 как выполненный. Грин приобрёл немалый опыт работы со строительными руками в ходе своих предыдущих амбициозных проектов. Грин передрал концепцию (вплоть до костяка) систем PULL и DFIRE. Экземпляр PULL должен захватывать следующий блок из длинной очереди и перемещать его поближе к машинам. Экземпляр DFIRE должен этот блок разрушать и отправлять глайдер перпендикулярно, направляя его в зону сборки. Получалась мешанина, состоявшая, однако, только из стационарных объектов. Важно отметить, что ни в один момент в сеттинге не присутствовало ни одного бродячего космического корабля. А глайдеры, отправлявшиеся в зону сборки, шли туда последовательным залпом. Это слегка ограниченный вариант последовательного залпа, но ранее было доказано, что такой залп является универсальным.

Грин и Гуше, создав простой PoC-шаблон, посылавший по паре PULL и DFIRE, объявили о собственном успехе. Чуть позже пользователь “Goldtiger997” показал, как синтезировать такой шаблон из 329 глайдеров. Это второй пункт из списка. Можно сгенерировать любую комбинацию из PULL-ов и DFIRE-ов, отодвигая обратно на нужное расстояние горстку глайдеров, составляющих корабль Кордера.

Дэйв Грин написал об этом в своём блоге и отметил, что для успешного достижения всех целей требуется построить очень много саморазрушающихся цепей прямо перед тем, как прибудет корабль Кордера. Это третий пункт списка. Никто этого не сделал, но участники удовлетворились, просто поверив, что это осуществимо.

Добиваемся ещё большего минимализма при помощи свич-двигателей

Вот вам ещё немного жаргона из игры «Жизнь»: свич-двигатель – это главная реакция корабля Кордера. Такой двигатель был открыт Чарльзом Кордерманом ещё в 1971 году, когда игра «Жизнь» всего год как существовало. Каждые 96 поколений этот двигатель проходит 8 клеток по диагонали. К сожалению, даже от единственного свич-двигателя остаётся столько мусора, что он в конечном итоге превращается в пустоту.

На кораблях Кордера устанавливается сразу по несколько свич-двигателей, работающих так, что мусор удаётся подчищать. Однако есть два способа стабилизировать конструкцию и с единственным свич-двигателем.

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

Второй вариант – это «глайдероделательный свич-двигатель». У него гораздо более громоздкий зольный шаблон, предполагающий, в частности, постоянное барражирование глайдеров в направлении движения.

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

Дешевле, беспорядочнее и столь же фуункционально

Глайдероделательный свич-двигатель (GPSE) движется с той же скоростью, что и корабль Кордера, создавая свой собственный предсказуемый поток глайдеров. Первые шаги по сокращению стоимости RCT-глайдера делаются путём замены большинства стационарных цепей на потоки глайдеров, выстреливаемых из GPSE. Всего 12 GPSE достаточно, чтобы заменить целый декодерный механизм, в результате чего в момент схождения получается гораздо более раскатистый «шлёп». Поскольку для синтеза GPSE требуется всего 4 глайдера, и именно декодерный механизм является самым дорогостоящим элементом такого синтеза, достаточно было исключить этот механизм, как стоимость всего обратного шестометателя рухнула до 59 глайдеров. Такое удешевление позволило выгрузить ещё больше работы во встроенный рецепт, и теперь для очистки требуется всего 12 зольных следов.

В течение 2018 года были открыты и другие варианты, позволившие сократить количество глайдеров до 35 – при внесении изменений в метод декодирования, но идея, в общем, была всё та же. Каждый из проектов был универсально функционален, а титаническая задача задействовать конструкцию так, чтобы она сама за собой прибирала, появилась уже постфактум и решена не была.

В течение следующих двух лет находки Криса Кейна и Адама Гуше позволили сэкономить ещё три глайдера, доведя их количество до 32. Затем в сентябре 2020 новый участник внёс улучшение, которое всех шокировало.

MathAndCode

Дэниэл Варгас по прозвищу MathAndCode появился на форумах в конце августа 2020 года. Первым делом он запостил тред, в котором обсуждал проект обратного шестометателя. Он спросил, почему приближающийся объект, кодирующий расстояние, обязательно должен быть каким-то вариантом корабля Кордера. Почему это не может быть одиночный GPSE? Двигатель GPSE обошёлся бы дешевле и мог бы разнообразнее использоваться.  

Адам Гуше дал хороший, но не идеальный ответ. Он сказал, что период у GPSE выше, и с этим связаны технические сложности. Представлялось, что заставить его работать будет сложнее. Но это не смутило MathAndCode, и он решил попытаться.

Менее чем через две недели он опубликовал пост “Потенциально универсальная конструкция из 16±2 глайдеров“.

Важнейшие реакции

Действительно, период у GPSE выше, чем у корабля Кордера – на облёт орбиты у него уходит 384 тика, а не 96. Здесь действует доплеровский эффект, поэтому при применении GPSE для обработки входящих глайдеров, поступающих от антипараллельного GPSE, требуется вернуть сигнал от двух разных взаимодействий, между которыми 192 тика.

Если в такой ситуации направить глайдер к приближающемуся GPSE, как это делалось по направлению к кораблю Кордера в сценарии с исходным RCT, то может произойти несколько вещей:

• GPSE разрушится (плохо)

• В пустоту будет выпущен бродячий глайдер, прибрать который никогда не получится (плохо)

• Произойдёт столкновение с каким-нибудь остаточным куском золы, в результате чего новый глайдер вернётся туда, откуда пришёл (хорошо)

• Один глайдер удаляется из потока GPSE, либо предотвращается создание такого глайдера (тоже хорошо!)

Последний вариант хорош, поскольку дырка в том месте, где мы ожидали бы встретить глайдер, в качестве сигнала не уступает по ценности глайдеру.

MathAndCode нашёл ключевую пару взаимодействий. Одно из них возвращало глайдер, а другое, отстоящее от первого на 192 тика, возвращало дырку. Таким образом можно было не только использовать GPSE вместо приближающегося корабля Кордера, но и сразу решалась проблема с «округлением вниз». Цепи, если их можно таковыми называть до сих пор, ещё сильнее упрощались.

Четыре GPSE и цель

После такой перестановки количество GPSE, требуемых для создания рабочего RCT, упало до четырёх.

Один кодирует рецепт.

Один предоставляет сигнальные глайдеры для взаимодействия и считывания чётности расстояний.

Ещё два, расположенные под прямым углом для координации цепей, подчищают все прочие глайдеры и выдают строительные команды для нулей и единиц.

Когда MathAndCode опубликовал свой пост, было не вполне ясно, являются ли доступные команды 0 и 1 поистине универсальным множеством. Но Адам Гуше прошерстил двоичные строки автоматизированным поиском – и надежда зажглась. Не учиняя никакой неустранимой путаницы, можно было выполнить всё необходимое при помощи следующих операций (текст цитируется по этому посту Адама):

• Подтягивание на 3fd и толчок на 4fd, в совокупности обеспечивающие fd-ходы с произвольными целочисленными значениями;

• Неразрушающая реакция с эмиссией глайдера;

• Разрушающая реакция с созданием блока, при которой блок выбрасывается за пределы всех дорожек при помощи одного или второго из вышеупомянутых методов;

• Подтягивание на 14fd, которое может следовать за операцией удвоения стремянки.

Это было универсальное множество. Поскольку 4 GPSE брали по 4 глайдера, а для первичного целевого объекта требовалось на один больше, MathAndCode скостил волшебное число с 32 до 17. Сообщество ликовало. Размышляли, есть ли ещё какие-нибудь уловки, чтобы заставить универсальный конструктор прибрать весь беспорядок. Но теоретически всё это казалось возможным. Верно?

И только вопрос об уборке не давал покоя

Как может стать, чтобы когда-либо удалось прибрать беспорядочные GPSE, оставляющие повсюду горы мусора? На каждый бит, считываемый конструктором, требовалось удваивать это количество мусора, поэтому нам требуется такое решение, при котором не важно, сколько мусора вообще на поле.

 

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

Разумеется, команде чистильщиков требовалось приступать к работе после того, как в середине всё уже было разбито. Соответственно, в конструкторе нужно было предусмотреть способ считывать сигнал, поступающий с большой задержкой. Кроме того, пятна в кодирующем потоке GPSE, где происходит считывание битов, очень отличались по составу мусора, и при уборке требовалось как-то справляться с этим. Но, всё же, сообщество понимало, как теоретически решить все эти проблемы.

Теория и преждевременная оптимизация

Оставшаяся часть задачи – связать тезисы «у нас есть универсальный конструктор» и «вот титаническая задача, которую должен решить этот конструктор». Примерно, как и при завершении Тихоходки, здесь мы имели дело со странной смесью рутины и первопроходческой работы. Можно сравнить с программированием-зубрёжкой на языке, которым ранее никто не пользовался.

Сообществу очень нравилось оптимизировать что-то такое, чего пока вообще не существует. Наплодились новые акронимы, самый важный из которых – DBCA (Декодер с Улучшенной Строительной Рукой). Фактически, DBCA был единственной сущностью, которую удалось построить при помощи универсального конструктора на материале универсального множества. Как только DBCA был построен, он начинал напрямую потреблять нули и единицы. Он собирал их в 9-разрядные кодоны для выполнения гораздо более мощных операций при помощи более функциональной строительной руки. Затрачивая множество битов на постройку того, что строить было не нужно, RCT теперь мог извлекать массу выгоды из каждого дополнительного бита. Выгода более чем окупается, хотя бы в процессе постройки кораблей-чистильщиков. В сообществе были уверены, что именно так следует минимизировать общее количество битов, необходимых для рецепта.

Технологические ограничения

Притом, что около 1 200 000 битов тратится на одно только создание DBCA, исходная дистанция должна быть порядка 2^1200000. К тому моменту, как построен DBCA, население вселенной в «Жизни» (в основном – мусор от GPSE) будет схожего порядка. Самый лучший эмулятор игры «Жизнь», возможно, обрабатывал бы популяции и поколения с численностью порядка 2¹⁰⁰⁰⁰, но это сильно превосходило пределы возможного.

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

Демо-паттерны превратились из 28 битов «правильного» RCT, с миллионом или более битов, вставленных между вторым и третьим сигналом RCT. Все они были разнесены таким образом, чтобы фундаментально вся система работала, как будто биты реально считываются из RCT, но теперь всё это должно поместиться в программе Golly.

Вот и финиш

Дэйв Грин, с восхитительным терпением приведший в порядок мириады логических линий, развиваемых в сообществе, составил официальный список проблем, оставшихся в проекте. Павел Гранковский (Pavgran, именно он был главным проектировщиком той части «Жизни» Конвея, которую я обсуждал в посте про тетрацию) методично вычёркивал из списка пункт за пунктом.

9 ноября Pavgran поделился шаблоном «семилятор» для сборки десятичного счётчика из 16 глайдеров. Он действительно мог проводить аккуратную уборку.

Считать сложно

16? В заголовке указано 15, а в работе MathAndCode удалось достичь только 17.

Что ж, на протяжении всего процесса технология оставалась одной и той же. Но в течение 2022 года пользователь, известная как dani или Даниэлла взялась за серьёзное и систематическое исследование свич-двигателей. Она нашла способ синтезировать пару GPSE, управляющих всеми цепями и строительством. Получилось всего 7 глайдеров, используемых вместе, а не 8 по отдельности. Pavgran, опубликовав полное демо для RCT 16, стал работать с dani, чтобы найти способ дальнейшего сокращения. Теперь они попытались удешевить создание первичной цели. В одном из альтернативных рецептов для GPSE из четырёх глайдеров выпускается бродячий глайдер, который мог бы быть подхвачен потоком от другого GPSE, примерно, как и дополнительный глайдер в более старом проекте. Потребуется обновить несколько первых битов, а также некоторую часть логики очистки, но во всём остальном конструкция будет работать точно как и раньше.

4 слева вверху, 4 справа внизу и 7 слева внизу, всего получается 15 глайдеров. Между ними замощено пустое пространство, в котором более 500 000 плиток.

На момент подготовки оригинала поста dani как раз поменяла статус аватара в  Discord на «чародейка свич-двигателей».

Разбор по битам

Для обновлённой 15-глайдерной конструкции десятичного счётчика нужны 1665791 бит. Большинство из них предоставляет семилятор, но 2 первых и 26 последних поступают из механизма RCT. Если бы исходная позиция была другой, то все биты поступали бы из RCT. (Ещё этот шаблон был бы настолько велик, что для его просмотра требовался бы новый специализированный эмулятор).

Если в общем виде разобрать, для чего используются эти биты, получится такой список:

1274729 – строим DBCA и передаём ему управление

192584 – строим новый конструктор, считывающий сохранённые данные, а не действительные сейчас

Последние 200093 битов сохраняются в Двоичном Хранилище и в Извлекающем Устройстве, именно эти 200093 бит перечислены ниже:

Происходит Большой Шлёп, после чего вся остальная информация считывается из хранилища

133900 – генеральная уборка

58173 – строится новая сущность (причём, в зависимости от конкретной сущности количество бит здесь будет отличаться)

8020 – конструктор завершает уборку (прибрав, в том числе, себя!) так, что в результате активируется зародышевая совокупность, а на поле остаётся только новопостроенная сущность

Отметим, что на сборку DBCA уходит примерно 75% всех доступных битов. Но оставшиеся 25% битов позволяют завершить 80% всей работы, это следует из количества глайдеров, получаемых в ходе последовательного залпа. Соответственно, при использовании более качественной строительной руки эффективность работы резко возрастает.

А теперь видео

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

Его я и записал для вас ниже. Приятного просмотра!