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