Клітинний автомат другого порядку

Кліти́нний автома́т дру́гого поря́дку — тип оборотного клітинного автомата (КА), який винайшов Едвард Фредкін,^[1][2] де стан клітини в момент часу t залежить не тільки від її сусідства в момент часу t − 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]

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

Якщо ми розглянемо два стани як булеві значення, цю відповідність між звичайним автоматом і автоматом другого порядку можна описати просто: стан клітини автомата другого порядку в момент часу t + 1 є результатом виключного або її стану в момент часу t − 1 зі станом, який правило звичайного клітинного автомата обчислило б для неї.^[4] Так можна створити всі правила другого порядку з двома станами.^[1] Отриманий автомат другого порядку, однак, загалом буде мало схожим на звичайний КА, з якого він був побудований. Правила другого порядку, створені в такий спосіб, Стівен Вольфрам назвав, додавши «R» до числа або коду Вольфрама^[en] базового правила.^[3]

Автомати другого порядку можна використати для моделювання більярдних комп’ютерів^[1] та моделі феромагнетизму Ізінга в статистичній механіці.^[2][4] Їх також можна використати в криптографії.^[5]