Клеточный автомат второго порядка - Second-order cellular automaton

Прошлые клетки, влияющие на состояние клетки во времени т в клеточном автомате 2-го порядка
Элементарное правило 18 СА (слева) и его аналог правила 18R второго порядка (справа). Время бежит вниз. Обратите внимание на асимметричные треугольники вверх / вниз в необратимом правиле.

А клеточный автомат второго порядка это тип обратимый клеточный автомат (CA) изобретен Эдвард Фредкин[1][2] где состояние клетки во время т зависит не только от своего соседства во времени т − 1, но и его состояние во времени т − 2.[3]

Общая техника

В общем, правило эволюции автомата второго порядка можно описать как функцию ж который отображает окрестность клетки на перестановка по состояниям автомата. На каждом временном шаге т, для каждой ячейки c автомата эта функция применяется к окрестности c дать перестановку σc. Тогда эта перестановка σc применяется к состоянию ячейки c вовремя т − 1, и результатом будет состояние ячейки во время т + 1. Таким образом, конфигурация автомата на каждом временном шаге вычисляется из двух предыдущих временных шагов: непосредственно предыдущий шаг определяет перестановки, которые применяются к ячейкам, а временной шаг перед этим дает состояния, на которых эти перестановки действуют. .[4]

Обратную временную динамику автомата второго порядка можно описать другим автоматом второго порядка с той же окрестностью, в которой функция грамм отображение окрестностей на перестановки дает обратную перестановку к ж. То есть по каждому возможному соседству N, ж(N) и грамм(N) должны быть обратные перестановки. При таком обратном правиле автомат, описываемый функцией грамм правильно вычисляет конфигурацию во время т − 1 из конфигураций на время т и т + 1. Поскольку каждый автомат второго порядка может быть обращен таким образом, отсюда следует, что все они обратимые клеточные автоматы, независимо от того, какая функция ж выбирается для определения правила автомата.[4]

Для автоматов с двумя состояниями

Если клеточный автомат имеет только два состояния, то возможны также только две возможные перестановки состояний: перестановка идентичности который отображает каждое состояние в себя, и перестановку, которая отображает каждое состояние в другое состояние. Мы можем отождествить эти две перестановки с двумя состояниями автомата. Таким образом, каждый клеточный автомат второго порядка (определяемый функцией от окрестностей к перестановкам) однозначно соответствует обычному (первого порядка) клеточному автомату, определяемому функционируют напрямую из районов в штаты.[4] Автоматы второго порядка с двумя состояниями симметричны относительно обращений времени: обращенная во времени динамика автомата может быть смоделирована с тем же правилом, что и исходная динамика.

Если мы рассмотрим два состояния как Логические значения, это соответствие между обычным автоматом и автоматом второго порядка можно описать просто: состояние клетки автомата второго порядка в момент времени т + 1 это Эксклюзивный или своего состояния во время т − 1 с состоянием, которое будет вычислять обычное правило клеточного автомата.[4] Фактически, все правила второго порядка с двумя состояниями могут быть получены таким образом.[1] Однако полученный автомат второго порядка будет мало похож на обычный СА, из которого он был построен. Построенные таким образом правила второго порядка называются Стивен Вольфрам добавив к номеру букву "R" или Код Wolfram базового правила.[3]

Приложения

Автоматы второго порядка могут использоваться для моделирования бильярдные компьютеры[1] и Модель Изинга из ферромагнетизм в статистическая механика.[2][4] Их также можно использовать для криптография.[5]

Рекомендации

  1. ^ а б c Марголус, Н. (1984), "Физические модели вычислений", Physica D, 10: 81–95, Дои:10.1016/0167-2789(84)90252-5. Перепечатано в Вольфрам, Стивен, изд. (1986), Теория и приложения клеточных автоматов, Расширенная серия по сложным системам, 1, World Scientific, стр. 232–246..
  2. ^ а б Vichniac, G. (1984), "Моделирование физики с помощью клеточных автоматов", Physica D, 10: 96–115, Дои:10.1016/0167-2789(84)90253-7.
  3. ^ а б Вольфрам, Стивен (2002), Новый вид науки, Вольфрам Медиа, стр.437–440, 452, ISBN  1-57955-008-8.
  4. ^ а б c d е Тоффоли, Томмазо; Марголус, Норман (1990), «Обратимые клеточные автоматы», Physica D, 45: 229–253, Дои:10.1016 / 0167-2789 (90) 90185-р. См. Особенно раздел 5.4 «Клеточные автоматы второго порядка», стр. 238–240. Этот выпуск Physica D был переиздан как Гутовиц, Говард, изд. (1991), Клеточные автоматы: теория и эксперимент, Массачусетский технологический институт / Северная Голландия.
  5. ^ Чай, Чжэньчуань; Цао, Чжэньфу; Чжоу, Юань (2005), «Шифрование на основе обратимых клеточных автоматов второго порядка», Параллельная и распределенная обработка и приложения (семинары ISPA 2005), Конспект лекций по информатике, Springer, стр. 350–358, Дои:10.1007/11576259_39.