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