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

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

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

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

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

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

Примеры [ править ]

Одномерные автоматы [ править ]

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

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

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

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

Существа [ править ]

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

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

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

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

Конструкции [ править ]

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

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

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

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

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

Моделирование необратимых автоматов [ править ]

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

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

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

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

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

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

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

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

Сохраненный ландшафт [ править ]

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

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

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

Теория [ править ]

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

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

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

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

Проверка обратимости [ править ]

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

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

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

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

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

Обратный размер соседства [ править ]

В одномерном обратимом клеточном автомате с n состояниями на ячейку, в котором окрестность ячейки представляет собой интервал из m ячеек, автомат, представляющий обратную динамику, имеет окрестности, состоящие не более чем из n m - 1 - m + 1 клеток. . Эта граница, как известно, является точной для m = 2 : существуют n- состояния обратимых клеточных автоматов с двухклеточными окрестностями, чья обращенная во времени динамика образует клеточный автомат с размером окрестности ровно n - 1 . [25]

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

Классификация Вольфрама [ править ]

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

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

Абстрактная алгебра [ править ]

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

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

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

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

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

Законы сохранения [ править ]

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

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

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

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

Приложения [ править ]

Решетчатые газовые автоматы [ править ]

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

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

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

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

Модель Изинга [ править ]

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

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

Вычисление бильярдного шара и маломощные вычисления [ править ]

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

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

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

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

(больше нерешенных задач по математике)

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

Синхронизация [ править ]

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

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

Шифрование [ править ]

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

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

Квантовые вычисления [ править ]

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

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

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

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

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

Заметки [ править ]

  1. ^ Вольфрам (2002) , стр. 1018 .
  2. ^ Шифф (2008) , стр. 44.
  3. ^ Toffoli & Margolus (1990) .
  4. ↑ Blanchard, Devaney & Keen (2004) , стр. 38 : «Карта сдвига, без сомнения, является фундаментальным объектом символической динамики».
  5. ^ a b Бойкетт (2004) .
  6. ^ Вольфрам (2002) , стр. 1093 .
  7. ^ Patt (1971) .
  8. ^ а б Сатнер (1991) .
  9. ^ a b c Тоффоли и Марголус (1987) , раздел 12.8.2, «Криттеры», стр. 132–134; Марголус (1999) ; Маротта (2005) .
  10. ^ a b c Тоффоли и Марголус (1987) , раздел 14.5, «Техника разбиения», стр. 150–153; Schiff (2008) , раздел 4.2.1, «Разбиение клеточных автоматов», стр. 115–116.
  11. ↑ Toffoli & Margolus (1987) , глава 12, «The Margolus Neighborhood», стр. 119–138.
  12. ^ а б Кари (2005) .
  13. ^ Margolus (1984) ; Vichniac (1984) ; Вольфрам (1984) .
  14. ^ a b c Тоффоли и Марголус (1987) , раздел 14.2, «Техника второго порядка», стр. 147–149. Вольфрам (2002) , стр. 437 и далее . Макинтош (2009) .
  15. ^ a b Тоффоли и Марголус (1990) , раздел 5.3, «Изменения сохраняемого ландшафта», стр. 237–238.
  16. ^ Миллер и Фредкин (2005) .
  17. ^ Миллер и Фредкин (2012) .
  18. ^ В одномерном случае некоторые из этих эквивалентностей уже были представлены на языке динамических систем, а не клеточных автоматов, Хедлундом (1969) , теорема 4.1. Для более высоких измерений см. Richardson (1972) и Di Gregorio & Trautteur (1975) .
  19. ^ Myhill (1963) .
  20. ^ Ричардсон (1972) .
  21. ^ Хедлунд (1969) .
  22. ^ Moraal (2000) .
  23. ^ Culik цитирует 1979 автоматную теорию учебника для этого результата, но увидеть БИЛ и др. (2003) для более поздних разработок по эффективному тестированию того, определяет ли датчик функцию.
  24. ^ Ни Аморосо и Патт (1972), ни Кулик (1987) не заявляют о временной сложности своих алгоритмов явно, но Сатнер (1991) делает это, и эту границу также можно найти, например, у Сезлера и Кари (2007) .
  25. ↑ Кари (1992) ; Чейслер (2004) ; Чейслер и Кари (2007) .
  26. ↑ Вольфрам (2002) , стр. 454–457.
  27. ^ Бойкетт (2004) . См. Hillman (1991) и Seck Tuoh Mora et al. (2005) за близкую работу по перечислению обратимых клеточных автоматов ширины 2.
  28. ^ Hattori & Takesue (1991) ; Фуксь (2007) .
  29. ^ a b Бойкетт, Кари и Таати (2008) .
  30. ^ Помо (1984) ; Takesue (1990) ; Капобианко и Тоффоли (2011) .
  31. ^ a b c Тоффоли и Марголус (1987) , глава 16, "Гидродинамика", стр. 172–184.
  32. ^ a b Тоффоли и Марголус (1987) , глава 17.2, «Системы Изинга», стр. 186–190.
  33. Перейти ↑ Durand-Lose (2002) .
  34. ^ Фредкин & Toffoli (1982) .
  35. ^ Кари ( 2005 , 2009 )
  36. ^ Toffoli & Margolus (1987) , раздел 12.8.3, "Асинхронное вычисление", стр. 134-136.
  37. ^ Мейер (1996) ; Шумахер и Вернер (2004) ; Шеперд, Франц и Вернер (2006) ; Нагадж и Вочян (2008) .
  38. ↑ См. Также « Физически универсальный клеточный автомат », оптимизированный для Штетла, Скотт Ааронсон , 26 июня 2014 г.

Ссылки [ править ]

  • Amoroso, S .; Patt, Ю. Н. (1972), "Decision процедуры сюрьективности и приемистости параллельных карт для тесселяции структур", журнал компьютерных и системных наук , 6 (5): 448-464, DOI : 10.1016 / S0022-0000 (72) 80013- 8 , Руководство MR  0317852.
  • Беаль, Мари-Пьер; Картон, Оливье; Приер, Кристоф; Sakarovitch Жак (2003), "ФОРМАТНО преобразователи: эффективная процедура для принятия решения о функциональности и последовательности", Теоретическая информатика , 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.
  • Boykett, Тим (2004), "Эффективные исчерпывающие перечни обратимых одномерным клеточных автоматов", Теоретическая информатика , 325 (2): 215-247, DOI : 10.1016 / j.tcs.2004.06.007 , MR  2086738.
  • Бойкетт, Тим; Кари, Джаркко ; Таати, Сиамак (2008), «Законы сохранения в прямоугольной CA» (PDF) , Journal of Cellular Automata , 3 (2): 115–122, MR  2394641 , архивировано из оригинала (PDF) 30 сентября 2015 г. CS1 maint: обескураженный параметр ( ссылка ).
  • Капобианко, Сильвио; Тоффоли, Томмазо (2011), «Можно ли спасти что-нибудь из теоремы Нётер для дискретных динамических систем?», Труды 10-й Международной конференции по нетрадиционным вычислениям (UC 2011) , Lecture Notes in Computer Science , 6714 , Springer-Verlag, pp. 77-88, Arxiv : 1103,4785 , DOI : 10.1007 / 978-3-642-21341-0_13.
  • Чай, Чжэньчуань; Цао, Чжэньфу; Чжоу, Юань (2005), «Шифрование на основе обратимых клеточных автоматов второго порядка», Параллельная и распределенная обработка и приложения (ISPA 2005 Workshops) , Lecture Notes in Computer Science , 3759 , Springer-Verlag, pp. 350–358, doi : 10.1007 / 11576259_39.
  • Кулик, Карел, И.И. (1987), "Об обратимых клеточных автоматах" (PDF) , Комплексные системы , 1 (6): 1035–1044, MR  0931401.
  • Cheizler, Eugen (2004), "О размере обратных окрестностей для одномерных обратимых клеточных автоматов", Теоретическая информатика , 325 (2): 273–284, DOI : 10.1016 / j.tcs.2004.06.009 , MR  2086740.
  • Чейслер, Ойген; Кари, Яркко (2007), "Жесткая линейная граница задержки синхронизации биективном автоматов", Теоретическая информатика , 380 (1-2): 23-36, DOI : 10.1016 / j.tcs.2007.02.052 , МР  2330639.
  • Di Gregorio, S .; Trautteur, G. (1975), "Об обратимости в клеточных автоматов", журнал компьютерных и системных наук , 11 (3): 382-391, DOI : 10.1016 / S0022-0000 (75) 80059-6 , MR  0392201.
  • Дюран-Лос, Жером (2001), "Представление обратимых клеточных автоматов с помощью обратимых блочных клеточных автоматов", Дискретные модели: комбинаторика, вычисления и геометрия (Париж, 2001 г.) , Discrete Math. Теор. Comput. Sci. Proc., AA, Maison Inform. Математика. Дискрет. (MIMD), Париж, стр. 145–154, MR  1888769.
  • Дюран-Лоз, Жером (2002), «Вычисления внутри модели бильярдного шара», в Adamatzky, Andrew (ed.), Collision-Based Computing , Springer-Verlag, стр. 135–160..
  • Фейнман, Ричард П. (1982), «Моделирование физики с помощью компьютеров», Международный журнал теоретической физики , 21 (6–7): 467–488, Bibcode : 1982IJTP ... 21..467F , doi : 10.1007 / BF02650179 , Руководство по ремонту  0658311 , S2CID  124545445 CS1 maint: обескураженный параметр ( ссылка ).
  • Фредкин, Эдвард ; Toffoli, Томмазо (1982), "Консервативная логика", Международный журнал теоретической физики , 21 (3-4): 219-253, Bibcode : 1982IJTP ... 21..219F , DOI : 10.1007 / BF01857727 , MR  0657156 , S2CID  37305161. Перепечатано в Adamatzky, Andrew , ed. (2002), Collision-Based Computing , Springer-Verlag, стр. 47–82..
  • Фуксь, Хенрик (2007), «Замечания о критическом поведении аддитивных инвариантов второго порядка в элементарных клеточных автоматах», Fundamenta Informaticae , 78 (3): 329–341, arXiv : nlin / 0502037 , Bibcode : 2005nlin ..... .2037F , Руководство по ремонту  2346870.
  • Хаттори, Тэцуя; Takesue, Синдзи (1991), "Добавка законсервирована величины в дискретное время решетки динамических систем", Physica D: нелинейные явления , 49 (3): 295-322, Bibcode : 1991PhyD ... 49..295H , DOI : 10.1016 / 0167-2789 (91) 90150-8 , MR  1115865.
  • Хедлунд, Г. А. (1969), "Эндоморфизмы и автоморфизмы сдвигового динамических систем", Математическая теория систем , 3 (4): 320-375, DOI : 10.1007 / BF01691062 , МР  0259881 , S2CID  21803927.
  • Хертлинг, Питер (1998), «Вложение клеточных автоматов в обратимые», Нетрадиционные модели вычислений (Окленд, 1998) , Серия Спрингера по дискретной математике и теоретической информатике, Springer-Verlag, стр. 243–256, MR  1653663.
  • Хиллман, Дэвид (1991), "Структура обратимых одномерных клеточных автоматов", Physica D: нелинейные явления , 52 (2–3): 277–292, Bibcode : 1991PhyD ... 52..277H , doi : 10.1016 / 0167-2789 (91) 90128-V , Руководство по ремонту  1128996.
  • Янцинг, Доминик (2010), Существует ли физически универсальный клеточный автомат или гамильтониан? , arXiv : 1009.1720 , Bibcode : 2010arXiv1009.1720J.
  • Kari, Яркко (1990), "Обратимость 2D клеточных автоматов неразрешима", Клеточные автоматы: теория и эксперимент (Лос - Аламос, Нью - Мексико, 1989), Physica D: Нелинейные явления , 45 (1-3): 379-385, Bibcode : 1990PhyD ... 45..379K , DOI : 10.1016 / 0167-2789 (90) 90195-У , МР  1094882.
  • Кари, Яркко (1992), «Об обратных окрестностях обратимых клеточных автоматов», Системы Линденмайера: Влияние на теоретическую информатику, компьютерную графику и биологию развития , Springer-Verlag, стр. 477–495, MR  1226709.
  • Кари, Яркко (1996), "Представление обратимых клеточных автоматов с блочных перестановок", Математическая теория систем , 29 (1): 47-61, DOI : 10.1007 / BF01201813 , МР  1360196 , S2CID  31986003.
  • Кари, Яркко (2005), «Обратимые клеточные автоматы» (PDF) , Развитие теории языков: 9-я международная конференция, DLT 2005, Палермо, Италия, 4–8 июля 2005 г., Труды , Лекционные заметки по информатике , 3572 , Springer . -Verlag, стр 2-23, DOI : 10.1007 / 11505877_5 , МР  2187250.
  • Кари, Яркко (2009), "Структура обратимых клеточных автоматов", Нетрадиционные вычисления: 8-я международная конференция, Калифорнийский университет в 2009 г., Понта-Делгада, Португалия, 7–11 сентября 2009 г., Труды , Лекционные заметки по компьютерным наукам , 5715 , Springer-Verlag , п. 6, Bibcode : 2009LNCS.5715 .... 6К , DOI : 10.1007 / 978-3-642-03745-0_5 , MR  2539690 CS1 maint: обескураженный параметр ( ссылка ).
  • Марголус, Норман (1984), "Физико-подобные модели вычислений", Physica D: нелинейные явления , 10 (1-2): 81-95, Bibcode : 1984PhyD ... 10 ... 81M , doi : 10.1016 / 0167 -2789 (84) 90252-5 , Руководство по ремонту  0762656. Перепечатано в Wolfram, Stephen (1986), Theory and Applications of Cellular Automata , Advanced series on complex systems, 1 , World Scientific, pp. 232–246., и в Adamatzky, Andrew , ed. (2002), Collision-Based Computing , Springer-Verlag, стр. 83–104..
  • Марголус, Норман (1999), «Кристаллические вычисления», в Hey, Anthony JG (ed.), Feynman and Computing, Perseus Books, стр. 267–305, arXiv : comp-gas / 9811002 , Bibcode : 1998comp.gas.11002M.
  • Маротта, Себастьян М. (2005), «Жизнь в мире животных » , Revista Ciências Exatas e Naturais , 7 (1), архивировано из оригинала 19 марта 2012 г. CS1 maint: обескураженный параметр ( ссылка ).
  • Макинтош, Гарольд В. (2009), "12. Обратимые клеточные автоматы", Одномерные клеточные автоматы , Luniver Press, стр. 205–246..
  • Мейер, Дэвид А. (1996), «От квантовых клеточных автоматов к квантовым решеточным газам», Journal of Statistical Physics , 85 (5–6): 551–574, arXiv : Quant-ph / 9604003 , Bibcode : 1996JSP ... .85..551M , DOI : 10.1007 / BF02199356 , МР  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 Pheniments , 141 (1-2): 1-18, Bibcode : 2000PhyD..141 .... 1M , doi : 10.1016 / S0167-2789 (00) 00020-8 , Руководство по ремонту  1764165.
  • Морита, Кенич (1995), "Реверсивное моделирование одномерных необратимых клеточных автоматов", Теоретическая информатика , 148 (1): 157-163, DOI : 10,1016 / 0304-3975 (95) 00038-X , MR  1347674.
  • Myhill, Джон (1963), "Обратное садово-из-Эдема теоремы Мура", Труды Американского математического общества , 14 (4): 685-686, DOI : 10,2307 / 2034301 , JSTOR  2034301 , MR  0155764 CS1 maint: обескураженный параметр ( ссылка ). Перепечатано в Burks, Arthur W. (1970), Essays on Cellular Automata , University of Illinois Press, стр. 204–205..
  • Нагадж, Даниэль; Wocjan, Pawel (2008), «Гамильтоновы квантовые клеточные автоматы в одном измерении», Physical Review A , 78 (3): 032311, arXiv : 0802.0886 , Bibcode : 2008PhRvA..78c2311N , doi : 10.1103 / PhysRevA.78.032311 , S2CID  18879990.
  • Патт, Ю.Н. (1971), Инъекции размера соседства три и четыре на множестве конфигураций из бесконечных одномерных автоматов тесселяции ячеек с двумя состояниями , Технический отчет ECON-N1-P-1, Ft. Монмут, Нью-Джерси 07703 CS1 maint: обескураженный параметр ( ссылка ). Цитируется Amoroso & Patt (1972) и Toffoli & Margolus (1990) .
  • Помо, Ю. (1984), «Инварианты в клеточных автоматах», Journal of Physics A: Mathematical and General , 17 (8): L415 – L418, Bibcode : 1984JPhA ... 17L.415P , doi : 10.1088 / 0305-4470 / 17/8/004 , Руководство по ремонту  0750565 CS1 maint: обескураженный параметр ( ссылка ).
  • Ричардсон, D. (1972), "Паркеты с локальными преобразованиями", Журнал вычислительной техники и систем наук , 6 (5): 373-388, DOI : 10.1016 / S0022-0000 (72) 80009-6 , MR  0319678.
  • Шеффер, Люк (2015), «Физически универсальный клеточный автомат», Труды 6 - го инноваций в теоретической информатике конференции (ITCS 2015) , Ассоциации по вычислительной технике , стр 237-246,. Дои : 10,1145 / 2688073,2688107 , S2CID  16903144 , ECCC  TR14-084.
  • Шифф, Джоэл Л. (2008), Клеточные автоматы: дискретный взгляд на мир , Wiley, ISBN 978-0-470-16879-0.
  • Шумахер, Б .; Вернер, РФ (2004), Обратимые квантовые клеточные автоматы , arXiv : Quant-ph / 0405174 , Bibcode : 2004quant.ph..5174S.
  • Сек Туох Мора, Хуан Карлос; Чапа Вергара, Серджио V .; Хуарес Мартинес, Хенаро; McIntosh, Гарольд V. (2005), "Процедура для вычисления обратимых одномерных клеточных автоматов" (PDF) , Physica D: нелинейные явления , 202 (1-2): 134-141, Bibcode : 2005PhyD..202..134S , DOI : 10.1016 / j.physd.2005.01.018 , МР  2131890.
  • Шепард, диджей; Franz, T .; Вернер, РФ (2006), «Универсально программируемый квантовый клеточный автомат», Physical Review Letters , 97 (2): 020502, arXiv : Quant-ph / 0512058 , Bibcode : 2006PhRvL..97b0502S , doi : 10.1103 / PhysRevLett.97.020502 , PMID  16907423 , S2CID  40900768.
  • Сатнер, Клаус (1991), "Графы Де Брейна и линейные клеточные автоматы" (PDF) , Комплексные системы , 5 : 19–30, MR  1116419 CS1 maint: обескураженный параметр ( ссылка ).
  • Такесуэ, Синдзи (1990), "Релаксационные свойства элементарных обратимых клеточных автоматов", Клеточные автоматы: теория и эксперимент (Лос-Аламос, Нью-Мексико, 1989), Physica D: нелинейные явления , 45 (1–3): 278–284, Bibcode : 1990PhyD ... 45..379K , DOI : 10.1016 / 0167-2789 (90) 90195-У , МР  1094882.
  • Toffoli, Томмазо (1977), "Расчет и построение универсальность обратимых клеточных автоматов", журнал компьютерных и системных наук , 15 (2): 213-231, DOI : 10.1016 / S0022-0000 (77) 80007-X , MR  0462816.
  • Тоффоли, Томмазо ; Марголус, Норман (1987), Машины клеточных автоматов: новая среда для моделирования , MIT Press, ISBN 9780262200608.
  • Тоффоли, Томмазо ; Марголус, Норман (1990), «Обратимые клеточные автоматы: обзор», Physica D: нелинейные явления , 45 (1–3): 229–253, Bibcode : 1990PhyD ... 45..229T , doi : 10.1016 / 0167- 2789 (90) 90185-Р , Руководство по ремонту  1094877.
  • Vichniac, Gérard Y. (1984), "Моделирование физики с помощью клеточных автоматов", Physica D: нелинейные явления , 10 (1-2): 96-115, Bibcode : 1984PhyD ... 10 ... 96V , doi : 10.1016 / 0167-2789 (84) 90253-7 , MR  0762657.
  • Уотроус, Джон (1995), «Об одномерных квантовых клеточных автоматах», Материалы 36-го ежегодного симпозиума по основам компьютерных наук (Милуоки, Висконсин, 1995) , Лос-Аламитос, Калифорния: IEEE Computer Society Press, стр. 528– 537, DOI : 10.1109 / SFCS.1995.492583 , MR  1619103 , S2CID  7441203 CS1 maint: обескураженный параметр ( ссылка ).
  • Вольфрам, Стивен (1984), «Клеточные автоматы как модели сложности» (PDF) , Nature , 311 (5985): 419–424, Bibcode : 1984Natur.311..419W , doi : 10.1038 / 311419a0 , S2CID  4237923.
  • Вольфрам, Стивен (2002), Новый вид науки , Wolfram Media, ISBN 1-57955-008-8, MR  1920418