Обратимый клеточный автомат

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

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

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

Свойства, присущие обратимым клеточным автоматам, могут быть использованы для изучения автоматов, которые необратимы, но имеют аттрактор — подмножество состояний, к которому сходятся случайные начальные состояния. Как пишет Стивен Вольфрам, «при приближении к аттрактору любая система, даже необратимая, проявляет некоторые свойства, близкие к обратимости»^[1].

Простейшие клеточные автоматы имеют одномерный массив ячеек, каждая из которых содержит 0 или 1, при том что окрестность ячейки состоит из неё самой и по одному соседу с каждой стороны; такие клеточные автоматы называются элементарными^[2]. Если функция перехода никогда не меняет состояние ячейки, всегда заменяет его на противоположное, заменяет его на состояние соседа (всегда одного и того же — слева или справа) или применяет комбинацию из последних двух операций, то такой элементарный клеточный автомат обратим. Несмотря на свою простоту, функция перехода, присваивающая каждой ячейке значение её соседа, играет важную роль в символической динамике, где она известна как оператор сдвига^[3].

Элементарные клеточные автоматы необратимы, не считая упомянутых выше тривиальных случаев, в которых каждая ячейка определяется состоянием только одного из своих соседей. Однако близко к обратимым правило 90, в котором будущее состояние каждой ячейки является суммой по модулю 2 (также известным как исключающее «ИЛИ», англ. XOR) текущих состояний её двух соседей. Хотя правило 90 необратимо, каждая его конфигурация имеет ровно четыре предшественника, а также правило 90 локально обратимо, то есть любая последовательность подряд идущих состояний имеет хотя бы одного предшественника^[4].

Немного более сложный пример получается так: пусть состояние каждой ячейки является упорядоченной парой (l,r), а функция перехода берёт левую часть нового состояния у соседа слева, а правую — справа. При этом мы предполагаем, что левая и правая части берутся из двух различных конечных множеств возможных значений. Пример изображён на иллюстрации в начале статьи: левая часть состояния — это форма фигуры, а правая — это её цвет. Такой автомат обратим, поскольку можно взять левую часть предыдущего состояния у ячейки справа, а правую — слева.

Другой пример обратимого одномерного клеточного автомата производит умножение на 2 или 5 в десятичной записи. Каждая цифра при таком умножении зависит только от двух предыдущих разрядов, а потому окрестность, определяющая следующее значение, конечна, что и необходимо для клеточного автомата. Вообще говоря, умножение или деление числа в позиционной записи на натуральное число n задаётся клеточным автоматом тогда и только тогда, когда все простые множители числа n входят в основание системы счисления. Такой автомат одномерен и обратим, поскольку можно поделить или умножить соответственно на то же число. И, например, умножение на 3 в десятичной записи не задаётся клеточным автоматом, поскольку может произойти перенос через сколь угодно большое число разрядов: при умножении 333334*3=1000002 происходит перенос через 5 разрядов^[5].

Игра «Жизнь», один из наиболее известных клеточных автоматов, не является обратимым: например, многие конфигурации вымирают. Также в нём существуют Сады Эдема — конфигурации без предшественников. Взамен Томмасо Тоффоли и Норман Марголус изобрели «Криттеров» — обратимый клеточный автомат с динамическим поведением, во многом схожим с «Жизнью»^[6].

«Криттеры» — блочный клеточный автомат, в котором ячейки разделены на блоки 2 × 2, обновляющиеся отдельно от остальных. При этом после каждого шага разделение на блоки меняется: они сдвигаются на одну ячейку по горизонтали и вертикали. Функция перехода «Криттеров» меняет состояние каждой ячейки на противоположное, если число живых ячеек в блоке не равняется двум, и вращает на 180° блок целиком, если это число равняется трём. Поскольку число живых ячеек меняется на число мёртвых, а функции перехода при каждом значении числа ячеек обратимы, такой клеточный автомат обратим на каждом блоке, а потому обратим в целом^[6].

Если начать с небольшого количества случайных ячеек внутри бо́льшего региона мёртвых ячеек, то из центрального региона распространится много маленьких шаблонов, подобных планеру из игры «Жизнь», которые будут сложным образом взаимодействововать. При этом «Криттеры» допускают сложные космические корабли и осцилляторы с бесконечным числом различных периодов^[6].

Известно несколько общих методов построения обратимых клеточных автоматов.

Блочный клеточный автомат — клеточный автомат, ячейки которого поделены на равные блоки, а функция перехода применяется к каждому блоку по отдельности. Обычно такой автомат по очереди использует несколько разбиений на блоки^[7]. Типичным примером такой схемы является окрестность Марголуса, в которой ячейки квадратной решётки поделены на блоки 2 × 2 вертикальными и горизонтальными прямыми, а после каждого шага разделение на блоки сдвигается на одну ячейку по горизонтали и вертикали; таким образом, все четыре ячейки любого блока оказываются в разных блоках на следующем шаге^[8]. «Криттеры», рассмотренные выше, используют окрестность Марголуса.

Чтобы блочный клеточный автомат был обратимым, необходимо и достаточно обратимости функции перехода на каждом блоке, что делает возможной проверку обратимости блочного клеточного автомата при помощи полного перебора. При этом обратный клеточный автомат тоже является блочным с такой же структурой разбиений на блоки, но обратной функцией перехода^[7].

Любой ${\displaystyle d}$-мерный клеточный автомат можно вложить в ${\displaystyle (d+1)}$-мерный обратимый: при этом каждое состояние нового автомата хранит всю историю эволюции старого. Используя это вложение, Тоффоли показал, что многие свойства необратимых клеточных автоматов переносятся на обратимые, например, они могут быть полны по Тьюрингу^[9].

Увеличение размерности в такой конструкции не случайно: при некоторых слабых ограничениях (вроде инвариантности вложения относительно параллельных переносов) доказано, что любое вложение клеточного автомата с «Садом Эдема», то есть конфигурацией без предшественников, в обратимый клеточный автомат должно увеличивать размерность^[10].

Однако, при наличии состояний покоя (англ. quiescent states), то есть состояний, которые не меняются при условии, что соседние состояния также не меняются^[], возможно моделирование конечной конфигурации клеточного автомата в блочном обратимом клеточном автомате той же размерности^[11]. Информация, которая должна была бы быть потеряна на следующем шаге, взамен хранится в бесконечном регионе из клеток, находящихся в состоянии покоя. При этом время, необходимое для моделирования части конфигурации, пропорционально её размеру. Тем не менее, такая конструкция позволяет доказать существование обратимого одномерного клеточного автомата, полного по Тьюрингу^[12].