Реверсивный клеточный автомат

Одномерный обратимый клеточный автомат с девятью состояниями. На каждом шаге каждая ячейка копирует форму своего левого соседа и цвет своего правого соседа.

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

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

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

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

Примеры

Одномерные автоматы

Клеточный автомат определяется его ячейками (часто одно- или двумерным массивом), конечным набором значений или состояний, которые могут войти в каждую ячейку, окрестностью, связывающей каждую ячейку с конечным набором соседних ячеек, и обновлением. правило , согласно которому значения всех ячеек обновляются одновременно в зависимости от значений соседних ячеек.Простейшие возможные клеточные автоматы имеют одномерный массив ячеек, каждая из которых может содержать двоичное значение (0 или 1), причем каждая ячейка имеет окрестность, состоящую только из нее и двух ее ближайших ячеек с каждой стороны; они называются элементарными клеточными автоматами . Если правило обновления для такого автомата заставляет каждую ячейку всегда оставаться в одном и том же состоянии, то автомат обратим: предыдущее состояние всех ячеек можно восстановить из их текущих состояний, поскольку для каждой ячейки предыдущее и текущее состояния являются такой же. Аналогично, если правило обновления заставляет каждую ячейку изменять свое состояние с 0 на 1 и наоборот, или если оно заставляет ячейку копировать состояние из фиксированной соседней ячейки, или если оно заставляет ее копировать состояние, а затем полностью изменить свое состояние. значение, оно обязательно обратимо. Тоффоли и Марголус (1990) называют такие типы обратимых клеточных автоматов, в которых состояние каждой ячейки зависит только от предыдущего состояния одной соседней клетки, «тривиальными». Несмотря на свою простоту, правило обновления, которое заставляет каждую ячейку копировать состояние соседней ячейки, важно в теории символьной динамики , где оно известно как карта сдвига .

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

Умножение десятичных чисел на два или на пять может выполняться одномерным обратимым клеточным автоматом с десятью состояниями на ячейку (десять десятичных цифр). Каждая цифра произведения зависит только от соседства двух цифр данного числа: цифры на той же позиции и цифры на одну позицию правее. В более общем смысле, умножение или деление дважды бесконечных последовательностей цифр в любом основании b на множитель или делитель x, все простые множители которого также являются простыми множителями b , представляет собой операцию, которая образует клеточный автомат, поскольку она зависит только от ограниченного числа. соседних цифр и является обратимым из-за существования мультипликативных обратных . Умножение на другие значения (например, умножение десятичных чисел на три) остается обратимым, но не определяет клеточный автомат, поскольку не существует фиксированного ограничения на количество цифр в исходном значении, необходимых для определения одной цифры в результат.

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

Правило тварей

Основная статья: Криттеры (клеточный автомат)

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

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

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

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

Конструкции

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

Блокировать клеточные автоматы

Основная статья: Блок клеточного автомата

Окрестность Марголуса для блочных клеточных автоматов. Разделение ячеек чередуется между набором блоков 2 × 2, обозначенным сплошными синими линиями, и набором блоков, обозначенным пунктирными красными линиями.

Блочный клеточный автомат — это автомат, в котором на каждом временном шаге ячейки автомата разбиваются на конгруэнтные подмножества (называемые блоками) и к каждому блоку независимо применяется одно и то же преобразование. Обычно такой автомат будет использовать более одного раздела на блоки и будет вращаться между этими разделами на разных временных шагах системы. В часто используемой форме этой конструкции, называемой окрестностью Марголуса, ячейки автомата образуют квадратную сетку и на каждом шаге разбиваются на более крупные квадратные блоки 2 × 2. Центр блока на одном временном шаге становится углом четырех блоков на следующем временном шаге, и наоборот; таким образом, четыре клетки в каждом 2 × 2 принадлежат четырем различным квадратам 2 × 2 предыдущего раздела. Правило Криттеров, обсуждавшееся выше, является примером автомата такого типа.

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

Моделирование необратимых автоматов

Тоффоли (1977) показал, как встроить любое необратимое d -мерное правило клеточного автомата в обратимое ( d + 1) -мерное правило. Каждый d -мерный срез нового обратимого правила моделирует один временной шаг исходного правила. Таким образом, Тоффоли показал, что многие особенности необратимых клеточных автоматов, такие как способность моделировать произвольные машины Тьюринга , также могут быть распространены на обратимые клеточные автоматы.

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

Морита (1995) описывает другой тип моделирования, который не подчиняется предположениям Гертлинга и не меняет размерность. Метод Мориты может моделировать конечные конфигурации любого необратимого автомата, в котором существует «спокойное» или «мертвое» состояние, например, если ячейка и все ее соседи покоятся, то ячейка остается неподвижной на следующем этапе. В моделировании используется обратимый блочный клеточный автомат той же размерности, что и исходный необратимый автомат. Информация, которая была бы уничтожена необратимыми действиями моделируемого автомата, вместо этого отправляется из конфигурации в бесконечную область покоя моделирующего автомата. Эта симуляция не обновляет все ячейки моделируемого автомата одновременно; скорее, время моделирования одного шага пропорционально размеру моделируемой конфигурации. Тем не менее, моделирование точно сохраняет поведение моделируемого автомата, как если бы все его ячейки обновлялись одновременно. С помощью этого метода можно показать, что даже одномерные обратимые клеточные автоматы способны к универсальным вычислениям.

Клеточные автоматы второго порядка

Прошлые клетки, влияющие на состояние клетки в момент времени t в клеточном автомате второго порядка

Одномерный клеточный автомат по Правилу 18 (слева) и производный от него клеточный автомат второго порядка (справа). В каждой строке изображения показана конфигурация автомата со временем, идущим вниз.

Основная статья: клеточный автомат второго порядка

Метод клеточного автомата второго порядка — это метод преобразования любого клеточного автомата в обратимый клеточный автомат, изобретенный Эдвардом Фредкиным и впервые опубликованный несколькими другими авторами в 1984 году. В этом методе состояние каждой ячейки автомата в момент времени t является функцией как ее окрестности в момент времени t - 1 , так и ее собственного состояния в момент времени t - 2 . В частности, функция перехода автомата отображает каждую окрестность в момент времени t - 1 в перестановку на множестве состояний, а затем применяет эту перестановку к состоянию в момент времени t - 2 . Обратная динамика автомата может быть вычислена путем сопоставления каждой окрестности с обратной перестановкой и действуя таким же образом.

В случае автоматов с двоичными состояниями (ноль или одно) существует только две возможные перестановки состояний (тождественная перестановка и перестановка, меняющая местами два состояния), которые сами могут быть представлены как исключающие или как состояние с двоичным значением. Таким образом, любой обычный двузначный клеточный автомат может быть преобразован в правило клеточного автомата второго порядка, используя функцию перехода обычного автомата для состояний в момент времени t - 1 , а затем вычисляя исключающее или из этих состояний с состояниями в момент времени t - 2, чтобы определить состояния в момент времени t . Однако определенное таким образом поведение обратимого клеточного автомата может не иметь никакого сходства с поведением клеточного автомата, из которого он был определен.

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

Сохраненный ландшафт

Одномерный клеточный автомат, обнаруженный Паттом (1971), использует окрестность, состоящую из четырех смежных ячеек. В этом автомате ячейка меняет свое состояние всякий раз, когда занимает знак "?" позиция в шаблоне «0?10». Никакие два таких шаблона не могут перекрываться, поэтому тот же «ландшафт», окружающий перевернутую ячейку, продолжает присутствовать после перехода. На следующем этапе ячейка в том же "?" положение снова перевернется, вернувшись в исходное состояние. Следовательно, этот автомат является обратным самому себе и обратим. Патт выполнил перебор всех одномерных клеточных автоматов с двумя состояниями и небольшими окрестностями; этот поиск привел к открытию этого автомата и показал, что это был простейший из возможных нетривиальных одномерных обратимых клеточных автоматов с двумя состояниями. Не существует нетривиальных обратимых автоматов с двумя состояниями и окрестностями из трех ячеек, и все обратимые автоматы с двумя состояниями и окрестностями из четырех ячеек являются простыми вариантами автомата Патта.

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

Модель SALT Миллера и Фредкина (2005) представляет собой особый случай техники консервативного ландшафта. В этой модели ячейки целочисленной сетки разбиваются на четное и нечетное подмножества. На каждом временном шаге определенные пары ячеек одной четности меняются местами в зависимости от конфигурации соседних ячеек другой четности. Правила, использующие эту модель, могут имитировать компьютер с бильярдным шаром . или поддерживать длинные цепочки живых клеток, которые могут двигаться с разными скоростями или вибрировать на разных частотах.

Теория

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

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

1. Каждая конфигурация автомата имеет уникального предшественника, сопоставленного с ней правилом обновления.
2. Правило обновления автомата является биекцией ; то есть функция, которая является одновременно взаимно однозначной и на .
3. Правило обновления является инъективной функцией , то есть не существует двух конфигураций, которые бы сопоставлялись с одной и той же общей конфигурацией. Это условие, очевидно, вытекает из предположения, что правило обновления является биекцией. С другой стороны, теорема «Райского сада» для клеточных автоматов подразумевает, что каждое инъективное правило обновления является биективным.
4. Обращенную во времени динамику автомата можно описать другим клеточным автоматом. Очевидно, что для того, чтобы это было возможно, правило обновления должно быть биективным. С другой стороны, если правило обновления является биективным, то оно имеет обратную функцию, которая также является биективной. Эта обратная функция должна быть правилом клеточного автомата. Для доказательства этого факта используется теорема Кертиса-Хедлунда-Линдона , топологическая характеристика правил клеточных автоматов как трансляционно-инвариантных функций, непрерывных относительно топологии Кантора на пространстве конфигураций.
5. Правило обновления автомата представляет собой автоморфизм динамической системы сдвига, определяемой пространством состояний и сдвигами решетки ячеек. То есть это гомеоморфизм , который коммутирует с отображением сдвига, как следует из теоремы Кертиса – Хедлунда – Линдона.

Ди Грегорио и Трауттер (1975) анализируют несколько альтернативных определений обратимости клеточных автоматов. Большинство из них оказываются эквивалентными либо инъективности, либо сюръективности переходной функции автомата; однако есть еще одна альтернатива, не соответствующая ни одному из этих двух определений. Это применимо к автоматам, таким как Игра Жизни, которые находятся в неподвижном или мертвом состоянии. В таком автомате конфигурацию можно определить как «конечную», если она имеет только конечное число нестационарных ячеек, и можно рассматривать класс автоматов, для которых каждая конечная конфигурация имеет хотя бы одного конечного предшественника. Этот класс оказывается отличным как от сюръективных, так и от инъективных автоматов, и в некоторых последующих исследованиях автоматы с этим свойством были названы обратимыми конечными автоматами .

Тестирование обратимости

Впервые было показано Аморосо и Паттом (1972) , что проблема проверки обратимости данного одномерного клеточного автомата имеет алгоритмическое решение. Альтернативные алгоритмы, основанные на теории автоматов и графах де Брейна, были предложены Куликом (1987) и Сатнером (1991) соответственно.

• Кулик начинает с наблюдения, что клеточный автомат имеет инъективную функцию перехода тогда и только тогда, когда функция перехода инъективна на подмножествах периодических конфигураций (бесконечно часто повторяющих одну и ту же подстроку в обоих направлениях). Он определяет недетерминированный преобразователь с конечным состоянием , который выполняет правило перехода автомата на периодических строках. Этот преобразователь работает, запоминая окрестности автомата в начале строки и переходя в состояние принятия, когда это соседство, объединенное с концом входных данных, приводит к тому, что его недетерминированно выбранные переходы становятся правильными. Затем Кулик меняет местами вход и выход преобразователя. Преобразователь, полученный в результате этой замены, моделирует обратную динамику данного автомата. Наконец, Кулик применяет ранее известные алгоритмы, чтобы проверить, сопоставляет ли полученный замененный преобразователь каждый вход с одним выходом.
• Сатнер определяет ориентированный граф (тип графа де Брёйна ), в котором каждая вершина представляет собой пару назначений состояний для ячеек в непрерывной последовательности ячеек. Длина этой последовательности выбирается на единицу меньше размера окрестности автомата. Ребро в графе Сатнера представляет собой пару последовательностей ячеек, которые перекрываются во всех ячейках, кроме одной, так что объединение последовательностей представляет собой полную окрестность клеточного автомата. Каждое такое ребро направлено от перекрывающейся подпоследовательности слева к подпоследовательности справа. Ребра включаются в граф только в том случае, если они представляют совместимые назначения состояний в перекрывающихся частях последовательностей ячеек и когда правило автомата (примененное к окрестностям, определяемым потенциальным ребром) дает одинаковые результаты для обоих назначений состояний. Выполняя анализ сильной связности этого графа за линейное время, можно определить, какие из его вершин принадлежат циклам. Правило перехода неинъективно тогда и только тогда, когда этот граф содержит направленный цикл , в котором хотя бы одна вершина имеет два разных назначения состояния.

Эти методы занимают полиномиальное время , пропорциональное квадрату размера таблицы переходов состояний входного автомата. Связанный алгоритм Хиллмана (1991) определяет, является ли данное правило сюръективным при применении к массивам ячеек конечной длины с периодическими граничными условиями, и если да, то для какой длины.

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

Однако для клеточных автоматов с другими окрестностями в двух или более измерениях проблема проверки обратимости неразрешима , а это означает, что не может существовать алгоритм, который всегда останавливается и всегда правильно отвечает на задачу. Доказательство этого факта Кари (1990) основано на ранее известной неразрешимости замощения плоскости плитками Ванга , наборами квадратных плиток с маркировкой на их краях, которые ограничивают, какие пары плиток могут располагаться от края до края. Кари определяет клеточный автомат из набора плиток Ванга, так что автомат не может быть инъективным тогда и только тогда, когда данный набор плиток может замостить всю плоскость. В его конструкции используется окрестность фон Неймана и ячейки с большим количеством состояний. В той же статье Кари также показал, что невозможно проверить, является ли данное правило клеточного автомата двух или более измерений сюръективным (то есть имеет ли оно райский сад ).

Обратный размер окрестности

В одномерном обратимом клеточном автомате с n состояниями на ячейку, в котором окрестностью ячейки является интервал из m клеток, автомат, представляющий обратную динамику, имеет окрестности, состоящие не более чем из n ^{м - 1} − m + 1 клеток. Известно, что эта граница точна для m = 2 : существуют обратимые клеточные автоматы с n состояниями и двухклеточными окрестностями, чья обращенная во времени динамика образует клеточный автомат с размером окрестности точно n − 1 .

Для любого целого числа m существует лишь конечное число двумерных обратимых клеточных автоматов с m -состоянием и окрестностью фон Неймана. Следовательно, существует четко определенная функция f ( m ) такая, что все реверсы клеточных автоматов с m -состояниями с окрестностью фон Неймана используют окрестность с радиусом не более f ( m ) : просто пусть f ( m ) будет максимальным, среди всех конечного числа обратимых клеточных автоматов с m -состояниями размера окрестности, необходимого для представления обращенной во времени динамики автомата. не существует Однако из-за результата Кари о неразрешимости алгоритма вычисления f ( m ) и значения этой функции должны расти очень быстро, быстрее, чем любая вычислимая функция .

Классификация Вольфрама

Известная классификация клеточных автоматов Стивена Вольфрама изучает их поведение при случайных начальных условиях. Для обратимого клеточного автомата, если начальная конфигурация выбирается равномерно случайным образом среди всех возможных конфигураций, то та же равномерная случайность продолжает сохраняться для всех последующих состояний. Таким образом, оказывается, что большинство обратимых клеточных автоматов относятся к классу 3 Вольфрама: автоматы, в которых почти все начальные конфигурации развиваются псевдослучайно или хаотично. Однако различить разные обратимые клеточные автоматы все же можно, анализируя влияние локальных возмущений на поведение автомата. Внесение изменений в исходное состояние обратимого клеточного автомата может привести к тому, что изменения в последующих состояниях останутся только в пределах ограниченной области, будут распространяться нерегулярно, но неограниченно или быстро распространяться, и Вольфрам (1984) перечисляет одномерные правила обратимого клеточного автомата. демонстрируя все три типа поведения.

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

Абстрактная алгебра

Другой способ формализовать обратимые клеточные автоматы включает абстрактную алгебру , и эта формализация оказалась полезна при разработке компьютеризированного поиска правил обратимых клеточных автоматов. Бойкетт (2004) определяет полуцентральный бигруппоид как алгебраическую структуру, состоящую из набора S элементов и двух операций → и ← над парами элементов, удовлетворяющих двум эквациональным аксиомам:

• для всех элементов a , b и c в S , ( a → b ) ← ( b → c ) = b , и
• для всех элементов a , b и c в S , ( a ← b ) → ( b ← c ) знак равно b .

Например, это верно для двух операций, в которых операция → возвращает правый аргумент, а операция ← возвращает левый аргумент.

Как утверждает Бойкетт, любой одномерный обратимый клеточный автомат эквивалентен автомату прямоугольной формы , в котором ячейки смещены на половину единицы на каждом временном шаге и в котором как прямая, так и обратная эволюция автомата имеют окрестности с две клетки, ячейки на расстоянии половины единицы в каждом направлении. Если обратимый автомат имеет окрестности размером более двух ячеек, его можно смоделировать обратимым автоматом с меньшими окрестностями и большим количеством состояний на ячейку, в котором каждая ячейка моделирующего автомата моделирует непрерывный блок ячеек в моделируемом автомате. Две аксиомы полуцентрального бигруппоида - это в точности условия, необходимые для того, чтобы функции прямого и обратного перехода этих двухклеточных окрестностей были обратными друг другу. То есть каждый полуцентральный бигруппоид определяет обратимый клеточный автомат прямоугольной формы, в котором функция перехода автомата использует операцию → для объединения двух ячеек его окрестности, и в котором Операция ← аналогичным образом определяет обратную динамику автомата. Каждый одномерный обратимый клеточный автомат эквивалентен автомату в этой форме.

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

Законы сохранения

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

Например, вспомните одномерный клеточный автомат, определенный на примере прямоугольной полосы , в котором состояния ячеек представляют собой пары значений ( l , r ), взятые из наборов L и R левых значений и правых значений, левого значения каждая ячейка перемещается вправо на каждом временном шаге, а правое значение каждой ячейки перемещается влево. В этом случае для каждого левого или правого значения x полосы можно определить сохраняющуюся величину — общее количество ячеек, имеющих это значение. Если существует λ левых значений и ρ правых значений, то существует λ + ρ − 2 независимых инварианта первого порядка, и любой инвариант первого порядка можно представить как линейную комбинацию этих фундаментальных. Сохраняющиеся величины, связанные с левыми значениями, текут равномерно вправо с постоянной скоростью: то есть, если количество левых значений, равных x, в пределах некоторой области C линии принимает определенное значение в момент времени 0 , то оно примет то же самое значение для сдвинутой области C + t /2 в момент времени t . Аналогично, сохраняющиеся величины, связанные с правыми значениями, равномерно текут влево.

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

В физических системах теорема Нётер обеспечивает эквивалентность законов сохранения и симметрии системы. Однако для клеточных автоматов эта теорема напрямую не применима, поскольку вместо того, чтобы управляться энергией системы , поведение автомата кодируется в ее правилах, и автомат гарантированно подчиняется определенным симметриям (трансляционной инвариантности как в пространстве, так и в пространстве). время) независимо от каких-либо законов сохранения, которым оно может подчиняться. Тем не менее, сохраняющиеся величины некоторых обратимых систем в некоторых отношениях ведут себя аналогично энергии. Например, если разные области автомата имеют разные средние значения некоторой сохраняющейся величины, правила автомата могут привести к тому, что эта величина рассеется, так что распределение количества будет более равномерным в более поздних состояниях. Использование этих сохраняющихся величин в качестве замены энергии системы может позволить анализировать ее с использованием методов классической физики.

Приложения

Решетчатые газовые автоматы

Основная статья: Решетчатый газовый автомат

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

В частности, модель решетчатого газа HPP состоит из частиц, движущихся с единичной скоростью в четырех направлениях, параллельных осям. Когда две частицы встречаются на одной линии в противоположных направлениях, они сталкиваются и отправляются наружу от точки столкновения на перпендикулярной линии. Эта система подчиняется законам сохранения физических газов и создает модели, внешний вид которых напоминает поведение физических газов. Однако было обнаружено, что он подчиняется нереальным дополнительным законам сохранения. Например, сохраняется общий импульс внутри любой отдельной линии. Кроме того, различия между осепараллельными и неосепараллельными направлениями в этой модели (ее анизотропия ) нежелательно велики. Модель решеточного газа FHP улучшает модель HPP, поскольку частицы движутся в шести разных направлениях под углом 60 градусов друг к другу, а не только в четырех направлениях. При любом лобовом столкновении две вылетающие частицы отклоняются под углом 60 градусов от двух входящих частиц. Трехсторонние столкновения также возможны в модели FHP и обрабатываются таким образом, чтобы сохранить общий импульс и избежать нефизических дополнительных законов сохранения модели HPP.

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

Модель Изинга

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

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

Вычисления на бильярдном шаре и вычисления с низким энергопотреблением

Фредкин и Тоффоли (1982) предложили компьютер с бильярдным шаром в рамках своих исследований обратимых вычислений . Компьютер с бильярдными шарами состоит из системы синхронизированных частиц (бильярдных шаров), движущихся по рельсам и направляемых фиксированным набором препятствий. Когда частицы сталкиваются друг с другом или с препятствиями, они испытывают упругое столкновение, с настоящими бильярдными шарами подобное тому, как это происходит . Входные данные в компьютер кодируются с использованием присутствия или отсутствия частиц на определенных входных дорожках, а его выходные данные кодируются аналогичным образом с использованием присутствия или отсутствия частиц на выходных дорожках. Сами дорожки можно представить как провода, а частицы — как логические сигналы, передаваемые по этим проводам. Когда частица сталкивается с препятствием, она отражается от него. Это отражение можно интерпретировать как изменение направления проволоки, по которой движется частица. Две частицы на разных дорожках могут столкнуться, образуя логический элемент в точке их столкновения.

Как показал Марголус (1984) , компьютеры с бильярдными шарами можно моделировать с использованием обратимого блочного клеточного автомата с двумя состояниями и окрестностью Марголуса. В правиле обновления этого автомата блоки, содержащие ровно одну живую ячейку, поворачиваются на 180°, блоки с двумя диагонально противоположными живыми ячейками поворачиваются на 90°, а все остальные блоки остаются неизменными. Эти правила заставляют изолированные живые клетки вести себя как бильярдные шары, движущиеся по диагональным траекториям. Связанные группы, состоящие из более чем одной живой клетки, вместо этого ведут себя как фиксированные препятствия компьютера с бильярдным шаром. В приложении Марголус также показал, что клеточный автомат второго порядка с тремя состояниями, использующий двумерную окрестность Мура, может моделировать компьютеры с бильярдными шарами.

Нерешенная задача по математике :

Каждый ли трехмерный обратимый клеточный автомат локально обратим?

(еще нерешенные задачи по математике)

Одна из причин изучения обратимых универсальных моделей вычислений, таких как модель бильярдного шара, заключается в том, что они теоретически могут привести к созданию реальных компьютерных систем, потребляющих очень мало энергии. Согласно принципу Ландауэра , необратимые вычислительные шаги требуют определенного минимального количества энергии на шаг, но обратимые шаги могут выполняться с количеством энергии на шаг, сколь угодно близким к нулю. Однако для выполнения вычислений с использованием меньшего количества энергии, чем предел Ландауэра, клеточному автомату недостаточно иметь глобально обратимую функцию перехода: требуется, чтобы локальное вычисление функции перехода также выполнялось в обратимый способ. Например, обратимые блочные клеточные автоматы всегда локально обратимы: поведение каждого отдельного блока предполагает применение обратимой функции с конечным числом входов и выходов. Тоффоли и Марголус (1990) были первыми, кто задался вопросом, имеет ли каждый обратимый клеточный автомат локально обратимое правило обновления. Кари (1996) показал, что для одно- и двумерных автоматов ответ положительный, а Дюран-Лозе (2001) показал, что любой обратимый клеточный автомат может быть смоделирован (возможно, другим) локально обратимым клеточным автоматом. Однако вопрос о том, является ли каждая обратимая переходная функция локально обратимой, остается открытым для размерностей больше двух.

Синхронизация

Прямолинейные формы, созданные правилом Трона

Правило «Трона» Тоффоли и Марголуса — это обратимое правило блокировки сотовой связи с соседством Марголуса. Когда все ячейки блока 2 × 2 имеют одинаковое состояние, все ячейки блока меняют состояние; во всех остальных случаях ячейки блока остаются неизменными. Как утверждают Тоффоли и Марголус, эволюцию шаблонов, генерируемых этим правилом, можно использовать как часы для синхронизации любого другого правила в окрестности Марголуса. Синхронизированный таким образом клеточный автомат подчиняется той же динамике, что и стандартное правило соседства Марголуса, при работе на асинхронном клеточном автомате .

Шифрование

Кари (1990) предложил использовать в качестве системы шифрования многомерные обратимые клеточные автоматы . В предложении Кари ключом шифрования будет правило клеточного автомата. Шифрование будет выполняться путем запуска правила на один шаг вперед, а расшифровка будет выполняться путем запуска его на один шаг назад. Кари предполагает, что подобную систему можно использовать в качестве криптосистемы с открытым ключом . В принципе, злоумышленник не может алгоритмически определить ключ дешифрования (обратное правило) по заданному ключу шифрования (прямое правило) из-за неразрешимости проверки обратимости, поэтому прямое правило может быть обнародовано без ущерба для безопасности системы. Однако Кари не уточнил, какие типы обратимых клеточных автоматов следует использовать для такой системы, и не показал, как криптосистема, использующая этот подход, сможет генерировать пары ключей шифрования/дешифрования.

Чай, Цао и Чжоу (2005) предложили альтернативную систему шифрования. В их системе ключ шифрования определяет локальное правило для каждой ячейки одномерного клеточного автомата. Автомат второго порядка, основанный на этом правиле, запускается на входе в течение нескольких раундов, чтобы преобразовать его в зашифрованный выход. Свойство обратимости автомата гарантирует, что любое зашифрованное сообщение можно расшифровать, запустив ту же систему в обратном порядке. В этой системе ключи должны храниться в секрете, поскольку один и тот же ключ используется как для шифрования, так и для дешифрования.

Квантовые вычисления

Основная статья: Квантовый клеточный автомат

Квантовые клеточные автоматы — это массивы автоматов, состояния и переходы между состояниями подчиняются законам квантовой динамики . Квантовые клеточные автоматы были предложены в качестве модели вычислений Фейнманом (1982) и впервые формализованы Уотрусом (1995) . Несколько конкурирующих представлений об этих автоматах все еще находятся в стадии исследования, многие из которых требуют, чтобы автоматы, построенные таким образом, были обратимыми.

Физическая универсальность

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

Шеффер (2015) построил обратимый клеточный автомат, физически универсальный в этом смысле. Автомат Шеффера представляет собой блочный клеточный автомат с двумя состояниями и окрестностью Марголиса, тесно связанный с автоматами для модели бильярдного шара и для решеточного газа ГПП. Однако модель бильярдного шара не является физически универсальной, поскольку ее можно использовать для построения непроницаемых стен, препятствующих чтению и преобразованию состояния в некоторой области. В модели Шеффера каждый узор в конечном итоге распадается на частицы, движущиеся по диагонали в четырех направлениях. Таким образом, его автомат не является по Тьюрингу полным . Однако Шеффер показал, что любую конечную конфигурацию можно окружить каркасом, который распадается медленнее, чем она. После того, как конфигурация разлагается на частицы, каркас перехватывает эти частицы и использует их в качестве входных данных для системы логических схем, построенных внутри каркаса. Эти схемы можно использовать для вычисления произвольных функций исходной конфигурации. Затем каркас преобразует выходные данные схем обратно в систему движущихся частиц, которые сходятся в исходной области и сталкиваются друг с другом, создавая копию преобразованного состояния. Таким образом, систему Шеффера можно использовать для применения любой функции к любой ограниченной области пространства состояний, показывая, что это автоматное правило физически универсально.

Ссылки

• Аморосо, С.; Патт, Ю.Н. (1972), «Процедуры принятия решения по сюръективности и инъективности параллельных отображений для структур тесселяции», Журнал компьютерных и системных наук , 6 (5): 448–464, doi : 10.1016/S0022-0000(72)80013- 8 , МР   0317852 .
• Беаль, Мари-Пьер; Картон, Оливье; Приер, Кристоф; Сакарович, Жак (2003), «Квадратные преобразователи: эффективная процедура определения функциональности и последовательности», Theoretical Computer Science , 292 (1): 45–63, doi : 10.1016/S0304-3975(01)00214-6 , MR   1964625 .
• Бланшар, Пол; Девани, Роберт Л .; Кин, Линда (2004), «Комплексная динамика и символическая динамика», в книге Уильямс, Сьюзен Г. (редактор), Символическая динамика и ее приложения , Труды симпозиумов по прикладной математике, том. 60, Провиденс, Род-Айленд: Американское математическое общество, стр. 37–60, doi : 10.1090/psapm/060/2078845 , MR   2078845 .
• Бойкетт, Тим (2004), «Эффективные исчерпывающие списки обратимых одномерных клеточных автоматов», Theoretical Computer Science , 325 (2): 215–247, doi : 10.1016/j.tcs.2004.06.007 , MR   2086738 .
• Бойкетт, Тим; Кари, Яркко ; Таати, Сиамак (2008), Законы сохранения в прямоугольных СА» (PDF) Журнал автоматов 3 ( 2): 115–122, MR   2394641 ; клеточных , , «
• Капобьянко, Сильвио; Тоффоли, Томмазо (2011), «Можно ли что-нибудь из теоремы Нётер спасти для дискретных динамических систем?», Труды 10-й Международной конференции по нетрадиционным вычислениям (UC 2011) , Конспекты лекций по информатике , том. 6714, Springer-Verlag, стр. 77–88, arXiv : 1103.4785 , doi : 10.1007/978-3-642-21341-0_13 , S2CID   42541816 .
• Чай, Чжэньчуань; Цао, Чжэньфу; Чжоу, Юань (2005), «Шифрование на основе обратимых клеточных автоматов второго порядка», Параллельная и распределенная обработка и приложения (семинары ISPA 2005) , Конспекты лекций по информатике , том. 3759, Springer-Verlag, стр. 350–358, doi : 10.1007/11576259_39 .
• Кулик, Карел II (1987), «Об обратимых клеточных автоматах» (PDF) , Сложные системы , 1 (6): 1035–1044, MR   0931401 .
• Цейцлер, Ойген (2004), «О размере обратных окрестностей одномерных обратимых клеточных автоматов», Theoretical Computer Science , 325 (2): 273–284, doi : 10.1016/j.tcs.2004.06.009 , MR   2086740 .
• Цейцлер, Ойген; Кари, Яркко (2007), «Точная линейная граница задержки синхронизации биективных автоматов», Theoretical Computer Science , 380 (1–2): 23–36, doi : 10.1016/j.tcs.2007.02.052 , MR   2330639 .
• Ди Грегорио, С.; Трауттер, Г. (1975), «Об обратимости в клеточных автоматах», Журнал компьютерных и системных наук , 11 (3): 382–391, doi : 10.1016/S0022-0000(75)80059-6 , MR   0392201 .
• Дюран-Лозе, Жером (2001), «Представление обратимых клеточных автоматов с помощью обратимых блочных клеточных автоматов», Дискретные модели: комбинаторика, вычисления и геометрия (Париж, 2001) , Дискретная математика. Теор. Вычислить. наук. Proc., А.А., Maison Inform. Математика. Дискретный. (MIMD), Париж, стр. 145–154, MR   1888769 .
• Дюран-Лозе, Жером (2002), «Вычисления внутри модели бильярдного шара», в Адамацки, Эндрю (ред.), Вычисления на основе столкновений , Springer-Verlag, стр. 135–160 .
• Фейнман, Ричард П. (1982), «Моделирование физики с помощью компьютеров», Международный журнал теоретической физики , 21 (6–7): 467–488, Бибкод : 1982IJTP...21..467F , doi : 10.1007/BF02650179 , МР   0658311 , S2CID   124545445 .
• Фредкин, Эдвард ; Тоффоли, Томмазо (1982), «Консервативная логика», Международный журнал теоретической физики , 21 (3–4): 219–253, Bibcode : 1982IJTP...21..219F , doi : 10.1007/BF01857727 , MR   0657156 , S2CID   37305161 . Перепечатано в Адамацкий, Эндрю , изд. (2002), Вычисления на основе столкновений , Springer-Verlag, стр. 47–82 .
• Фукс, Хенрик (2007), «Замечания о критическом поведении аддитивных инвариантов второго порядка в элементарных клеточных автоматах», Fundamenta Informaticae , 78 (3): 329–341, arXiv : nlin/0502037 , Bibcode : 2005nlin..... .2037F , МР   2346870 .
• Хаттори, Тецуя; Такесуэ, Синдзи (1991), «Аддитивные сохраняющиеся величины в решеточных динамических системах с дискретным временем», Physica D: Nonlinear Phenomena , 49 (3): 295–322, Бибкод : 1991PhyD...49..295H , doi : 10.1016/ 0167-2789(91)90150-8 , МР   1115865 .
• Хедлунд, Г. А. (1969), «Эндоморфизмы и автоморфизмы динамических систем сдвига», Mathematical Systems Theory , 3 (4): 320–375, doi : 10.1007/BF01691062 , MR   0259881 , S2CID   21803927 .
• Хертлинг, Питер (1998), «Вложение клеточных автоматов в обратимые», Нетрадиционные модели вычислений (Окленд, 1998) , Серия Спрингера по дискретной математике и теоретической информатике, Springer-Verlag, стр. 243–256, MR   1653663 .
• Хиллман, Дэвид (1991), «Структура обратимых одномерных клеточных автоматов», Physica D: Nonlinear Phenomena , 52 (2–3): 277–292, Бибкод : 1991PhyD...52..277H , doi : 10.1016 /0167-2789(91)90128-В , МР   1128996 .
• Янцинг, Доминик (2010), Существует ли физически универсальный клеточный автомат или гамильтониан? , arXiv : 1009.1720 , Bibcode : 2010arXiv1009.1720J .
• Кари, Яркко (1990), «Обратимость двумерных клеточных автоматов неразрешима», Клеточные автоматы: теория и эксперимент (Лос-Аламос, Нью-Мексико, 1989), Physica D: Nonlinear Phenomena , 45 (1–3): 379–385, Bibcode : 1990PhyD...45..379К , doi : 10.1016/0167-2789(90)90195-У , МР   1094882 .
• Кари, Яркко (1992), «Об обратных окрестностях обратимых клеточных автоматов», Системы Линденмайера: влияние на теоретическую информатику, компьютерную графику и биологию развития , Springer-Verlag, стр. 477–495, doi : 10.1007/978- 3-642-58117-5_29 , МР   1226709 .
• Кари, Яркко (1996), «Представление обратимых клеточных автоматов с перестановками блоков», Mathematical Systems Theory , 29 (1): 47–61, doi : 10.1007/BF01201813 , MR   1360196 , S2CID   31986003 .
• Кари, Яркко (2005), «Обратимые клеточные автоматы» (PDF) , Развитие теории языка: 9-я Международная конференция, DLT 2005, Палермо, Италия, 4–8 июля 2005 г., Труды , Конспекты лекций по информатике , том. 3572, Springer-Verlag, стр. 2–23, номер документа : 10.1007/11505877_5 , MR   2187250 .
• Кари, Яркко (2009), «Структура обратимых клеточных автоматов», Нетрадиционные вычисления: 8-я Международная конференция, Калифорнийский университет, 2009 г., Понта-Делгада, Португалия, 7–11 сентября 2009 г., Труды , Конспекты лекций по информатике , том. 5715, Шпрингер-Верлаг, с. 6, Bibcode : 2009LNCS.5715....6K , номер doi : 10.1007/978-3-642-03745-0_5 , MR   2539690 .
• Марголус, Норман (1984), «Физико-подобные модели вычислений», Physica D: Nonlinear Phenomena , 10 (1–2): 81–95, Бибкод : 1984PhyD...10...81M , doi : 10.1016/0167 -2789(84)90252-5 , МР   0762656 . Перепечатано в Вольфрам, Стивен (1986), Теория и приложения клеточных автоматов , Расширенная серия по сложным системам, том. 1, World Scientific, стр. 232–246, Bibcode : 1986taca.book.....W , и в Адамацкий, Эндрю , изд. (2002), Вычисления на основе столкновений , Springer-Verlag, стр. 83–104 .
• Марголус, Норман (1999), «Кристаллические вычисления», в книге «Эй, Энтони Дж. Г. (ред.), Фейнман и вычисления» , Perseus Books, стр. 267–305, arXiv : comp-gas/9811002 , Bibcode : 1998comp.gas.11002M .
• Маротта, Себастьян М. (2005), «Жизнь в мире тварей» , Revista Ciências Exatas e Naturais , 7 (1), заархивировано из оригинала 19 марта 2012 г.
• Макинтош, Гарольд В. (2009), «12. Обратимые клеточные автоматы», Одномерные клеточные автоматы , Luniver Press, стр. 205–246 .
• Мейер, Дэвид А. (1996), «От квантовых клеточных автоматов к квантовым решеточным газам», Журнал статистической физики , 85 (5–6): 551–574, arXiv : quant-ph/9604003 , Bibcode : 1996JSP... .85..551M , doi : 10.1007/BF02199356 , MR   1418805 , S2CID   661940 .
• Миллер, Дэниел Б.; Фредкин, Эдвард (2005), «Обратимые универсальные клеточные автоматы с двумя состояниями в трех измерениях», Труды 2-й конференции по вычислительным возможностям (CF '05) , Нью-Йорк, Нью-Йорк, США: ACM, стр. 45–51. , arXiv : nlin/0501022 , doi : 10.1145/1062261.1062271 , ISBN  1-59593-019-1 , S2CID   14082792 .
• Миллер, Дэниел Б.; Фредкин, Эдвард (2012), Круговое движение струн в клеточных автоматах и ​​другие сюрпризы , arXiv : 1206.2060 , Bibcode : 2012arXiv1206.2060M .
• Мораал, Хендрик (2000), «Теоретико-графовая характеристика обратимых клеточных автоматов», Physica D: Nonlinear Phenomena , 141 (1–2): 1–18, Bibcode : 2000PhyD..141....1M , doi : 10.1016 /S0167-2789(00)00020-8 , МР   1764165 .
• Морита, Кеничи (1995), «Обратимое моделирование одномерных необратимых клеточных автоматов», Theoretical Computer Science , 148 (1): 157–163, doi : 10.1016/0304-3975(95)00038-X , MR   1347674 .
• Майхилл, Джон (1963), «Обратная теорема Мура об Эдемском саду», Proceedings of the American Mathematical Society , 14 (4): 685–686, doi : 10.2307/2034301 , JSTOR   2034301 , MR   0155764 . Перепечатано в Беркс, Артур В. (1970), Очерки клеточных автоматов , University of Illinois Press, стр. 204–205 .
• Нагадж, Дэниел; Воцян, Павел (2008), «Гамильтоновы квантовые клеточные автоматы в одном измерении», Physical Review A , 78 (3): 032311, arXiv : 0802.0886 , Bibcode : 2008PhRvA..78c2311N , doi : 10.1103/PhysRevA.78.032311 S , 2CID   18879990 .
• Патт, Ю.Н. (1971), Инъекции размера окрестности три и четыре в набор конфигураций из бесконечных одномерных автоматов тесселяции ячеек с двумя состояниями , Технический отчет ECON-N1-P-1, Ft. Монмут, Нью-Джерси 07703 . Цитируется Аморосо и Паттом (1972) и Тоффоли и Марголусом (1990) .
• Помо, Ю. (1984), «Инварианты в клеточных автоматах», Journal of Physics A: Mathematical and General , 17 (8): L415–L418, Бибкод : 1984JPhA...17L.415P , doi : 10.1088/0305-4470 /17.08.004 , МР   0750565 .
• Ричардсон, Д. (1972), «Тесселяции с локальными преобразованиями», Журнал компьютерных и системных наук , 6 (5): 373–388, doi : 10.1016/S0022-0000(72)80009-6 , MR   0319678 .
• Шеффер, Люк (2015), «Физически универсальный клеточный автомат», Труды 6-й конференции по инновациям в теоретической информатике (ITCS 2015) , Ассоциация вычислительной техники , стр. 237–246, doi : 10.1145/2688073.2688107 , S2CID   16903144 , ЕССС   ТР14-084 .
• Шифф, Джоэл Л. (2008), Клеточные автоматы: дискретный взгляд на мир , Wiley, ISBN  978-0-470-16879-0 .
• Шумахер, Б .; Вернер, РФ (2004), Обратимые квантовые клеточные автоматы , arXiv : quant-ph/0405174 , Bibcode : 2004quant.ph..5174S .
• Сек Туох Мора, Хуан Карлос; Чапа Вергара, Серджио В.; Хуарес Мартинес, Хенаро; Макинтош, Гарольд В. (2005), «Процедуры расчета обратимых одномерных клеточных автоматов» (PDF) , Physica D: Nonlinear Phenomena , 202 (1–2): 134–141, Bibcode : 2005PhyD..202..134S , doi : 10.1016/j.physd.2005.01.018 , МР   2131890 .
• Шепард, диджей; Франц, Т.; Werner, RF (2006), «универсально программируемый квантовый автоматический автомат», « Письма для физического обзора » , 97 (2): 020502, arxiv : Quant-ph/0512058 , Bibcode : 2006 phrvl..97b0502S , doi : 10.1103/physrevlett.97.050502 ,. PMID   16907423 , S2CID   40900768 .
• Сатнер, Клаус (1991), «Графы Де Брейна и линейные клеточные автоматы» (PDF) , Complex Systems , 5 : 19–30, MR   1116419 .
• Такесуэ, Синдзи (1990), «Релаксационные свойства элементарных обратимых клеточных автоматов», Клеточные автоматы: теория и эксперимент (Лос-Аламос, Нью-Мексико, 1989), Physica D: Nonlinear Phenomena , 45 (1–3): 278–284, Bibcode : 1990PhyD...45..379К , doi : 10.1016/0167-2789(90)90195-У , МР   1094882 .
• Тоффоли, Томмазо (1977), «Универсальность вычислений и построения обратимых клеточных автоматов», Журнал компьютерных и системных наук , 15 (2): 213–231, doi : 10.1016/S0022-0000(77)80007-X , MR   0462816 .
• Тоффоли, Томмазо ; Марголус, Норман (1987), Клеточные автоматы: новая среда для моделирования , MIT Press, ISBN  978-0-262-20060-8 .
• Тоффоли, Томмазо ; Марголус, Норман (1990), «Обратимые клеточные автоматы: обзор», Physica D: Nonlinear Phenomena , 45 (1–3): 229–253, Бибкод : 1990PhyD...45..229T , doi : 10.1016/0167- 2789(90)90185-Р , МР   1094877 .
• Вишняк, Жерар Ю. (1984), «Моделирование физики с помощью клеточных автоматов», Physica D: Nonlinear Phenomena , 10 (1–2): 96–115, Бибкод : 1984PhyD...10...96V , doi : 10.1016/ 0167-2789(84)90253-7 , МР   0762657 .
• Уотроус, Джон (1995), «Об одномерных квантовых клеточных автоматах», Труды 36-го ежегодного симпозиума по основам информатики (Милуоки, Висконсин, 1995) , Лос-Аламитос, Калифорния: IEEE Computer Society Press, стр. 528– 537, doi : 10.1109/SFCS.1995.492583 , MR   1619103 , S2CID   7441203 .
• Вольфрам, Стивен (1984), «Клеточные автоматы как модели сложности» (PDF) , Nature , 311 (5985): 419–424, Бибкод : 1984Natur.311..419W , doi : 10.1038/311419a0 , S2CID   4237923 .
• Вольфрам, Стивен (2002), Новый вид науки , Wolfram Media, ISBN  1-57955-008-8 , МР   1920418