Кліти́нний автома́т дру́гого поря́дку — тип оборотного клітинного автомата (КА), який винайшов Едвард Фредкін,. Reprinted in .. де стан клітини в момент часу залежить не тільки від її сусідства в момент часу , але також від її стану в момент часу ..
Загальна техніка Загалом, правило еволюції для автомата другого порядку можна описати як функцію , яка відображає окіл клітини на перестановку на станах автомата. На кожному кроці часу для кожної клітини автомата ця функція застосовується до околу , щоб отримати перестановку . Потім ця перестановка застосовується до стану клітини в момент часу , і результатом є стан клітини в момент часу . Отже, конфігурація автомата на кожному часовому кроці обчислюється з двох попередніх часових кроків: безпосередньо попередній крок визначає перестановки, які застосовують до клітин, а часовий крок перед ним дає стани, на яких діють ці перестановки.. See especially section 5.4 "Second-order cellular automata", pp. 238–240. This issue of Physica D was reprinted as .
Обернену часову динаміку автомата другого порядку можна описати іншим автоматом другого порядку з таким самим околом, у якому функція що відображає околи на перестановки, дає зворотну перестановку на . Тобто, на кожному можливому околі , і повинні бути зворотні перестановки. За допомогою цього зворотного правила автомат, описаний функцією , правильно обчислює конфігурацію в момент часу з конфігурацій в момент часу і . Оскільки кожен автомат другого порядку можна так обернути, з то всі вони є оборотними клітинними автоматами, незалежно від того, яку функцію вибрано для визначення правила автомата.
Для автоматів з двома станами Якщо клітинний автомат має лише два стани, то також є лише дві можливі перестановки станів: , яка відображає кожен стан на себе, і перестановка, яка відображає кожен стан на інший стан. Можна ототожнити ці дві перестановки з двома станами автомата. Таким чином, кожен клітинний автомат другого порядку (визначений функцією із околів у перестановки) однозначно відповідає звичайному клітинному автомату (першого порядку), визначеному функцією безпосередньо із околів у стани. Автомати другого порядку з двома станами симетричні відносно обернень часу: динаміку автомата, обернену в часі, можна змоделювати за тим самим правилом, що й початкову динаміку.
Якщо ми розглянемо два стани як булеві значення, цю відповідність між звичайним автоматом і автоматом другого порядку можна описати просто: стан клітини автомата другого порядку в момент часу є результатом виключного або її стану в момент часу зі станом, який правило звичайного клітинного автомата обчислило б для неї. Так можна створити всі правила другого порядку з двома станами. Отриманий автомат другого порядку, однак, загалом буде мало схожим на звичайний КА, з якого він був побудований. Правила другого порядку, створені в такий спосіб, Стівен Вольфрам назвав, додавши «R» до числа або базового правила.
Застосування Автомати другого порядку можна використати для моделювання більярдних комп’ютерів та моделі феромагнетизму Ізінга в статистичній механіці. Їх також можна використати в криптографії..
Примітки