Оборотний клітинний автомат

Оборотний клітинний автомат — клітинний автомат, у якому кожен стан має єдиного попередника. Таким чином, це регулярна ґратка з комірок, стан кожної з яких береться зі скінченної множини станів, і правило для одночасного оновлення станів комірок, виходячи зі станів їхніх сусідів. Умова оборотності полягає в тому, що попередній стан будь-якої комірки можна визначити, знаючи оновлені стани всіх комірок ґратки. Після обернення часу виходить інший оборотний клітинний автомат, можливо зі значно ширшим околом, але також із правилом для визначення майбутнього стану комірки, виходячи з поточних станів її сусідів.

Відомо кілька методів задавання оборотних клітинних автоматів, зокрема блокових клітинних автоматів, у яких кожен блок оновлюється незалежно від інших, і клітинних автоматів другого порядку, в яких правило оновлення комірок визначається двома попередніми станами автомата. Разом з тим, якщо автомат задано за допомогою таблиці правил, задача перевірки його оборотності розв'язна для одновимірного клітинного автомата, але нерозв'язна в загальному випадку.

Оборотні клітинні автомати задають природну модель оборотних обчислень — технології, яка дозволяє створити обчислювальні пристрої з дуже низьким споживанням електроенергії. Квантові клітинні автомати, які дають змогу проводити обчислення з використанням принципів квантової механіки, часто передбачаються оборотними. Крім того, багато фізичних моделей, такі як рух молекул ідеального газу або модель Ізінга розміщення магнітних зарядів, природно оборотні і моделюються оборотними клітинними автоматами.

Властивості оборотних клітинних автоматів можна використати для вивчення автоматів, які є необоротними, але мають атрактор — підмножину станів, до якої збігаються випадкові початкові стани. Як пише Стівен Вольфрам, «при наближенні до атрактора будь-яка система, навіть необоротна, виявляє деякі властивості, близькі до оборотності»^[1]

Найпростіші клітинні автомати мають одновимірний масив комірок, кожна з яких містить 0 або 1, при тому, що окіл комірки складається з неї самої і по одному сусіду з кожного боку; такі клітинні автомати називають елементарними.^[2] Якщо функція переходу ніколи не змінює стану комірки, завжди змінює його на протилежний, змінює його на стан сусіда (завжди одного й того ж — ліворуч або праворуч) або застосовує комбінацію з останніх двох операцій, то такий елементарний клітинний автомат оборотний. Попри простоту, функція переходу, що присвоює кожній комірці значення її сусіда, відіграє важливу роль у символічній динаміці, де вона відома як оператор зсуву.^[3]

Елементарні клітинні автомати необоротні, крім згаданих вище очевидних випадків, у яких кожна комірка визначається станом лише одного зі своїх сусідів. Однак близьке до оборотних правило 90, в якому майбутній стан кожної комірки є сумою за модулем 2 (також відомою як виключне «АБО»,англ. XOR) поточних станів її двох сусідів. Хоча правило 90 необоротне, кожна його конфігурація має рівно чотири попередники, а також правило 90 локально оборотне, тобто будь-яка послідовність станів, що йдуть підряд, має хоча б одного попередника.^[4]

Трохи складніший приклад: нехай стан кожної комірки є впорядкованою парою (l, r), а функція переходу бере ліву частину нового стану в сусіда ліворуч, а праву — праворуч. При цьому ми припускаємо, що ліва та права частини беруться з двох різних скінченних множин можливих значень. Приклад зображено на ілюстрації на початку статті: ліва частина стану — це форма фігури, а права — її колір. Такий автомат оборотний, оскільки можна взяти ліву частину попереднього стану з комірки праворуч, а праву — ліворуч.

Інший приклад оборотного одновимірного клітинного автомата здійснює множення на 2 або 5 у десятковому записі. Кожна цифра за такого множення залежить тільки від двох попередніх розрядів, а тому окіл, що визначає наступне значення, скінченний, що необхідно для клітинного автомата. Загалом, множення або ділення числа в позиційному записі на натуральне число ${\displaystyle n}$ задається клітинним автоматом тоді й лише тоді, коли всі прості множники числа ${\displaystyle n}$ входять в основу системи числення. Такий автомат одновимірний і оборотний, оскільки можна поділити або помножити відповідно на те саме число. І, наприклад, множення на 3 в десятковому записі не задається клітинним автоматом, оскільки може відбутися перенесення через як завгодно багато розрядів: при множенні 333334 * 3 = 1000002 відбувається перенесення через 5 розрядів.^[5]

Один з найвідоміших клітинних автоматів — гра «Життя», не є оборотним: наприклад, багато конфігурацій вимирають. Також у ньому є едемські сади — конфігурації без попередників. Натомість Томмасо Тоффолі та Норман Марґолус винайшли «Критерів» — оборотний клітинний автомат із динамічною поведінкою, багато в чому схожою на «Життя».^[6]

«Критери» — блоковий клітинний автомат, у якому комірки розділено на блоки 2×2, що оновлюються окремо від інших. При цьому після кожного кроку поділ на блоки змінюється: вони зсуваються на одну комірку по горизонталі та вертикалі. Функція переходу «Критерів» змінює стан кожної комірки на протилежний, якщо кількість живих комірок у блоці не дорівнює двом, і обертає блок цілком на 180 °, якщо це число дорівнює трьом. Оскільки кількість живих комірок змінюється на кількість мертвих, а функції переходу при кожному значенні кількості комірок оборотні, такий клітинний автомат оборотний на кожному блоці, а тому оборотний у цілому.^[6]

Якщо почати з невеликої кількості випадкових комірок усередині великої ділянки мертвих комірок, то з центральної ділянки пошириться багато маленьких шаблонів, подібних до планера з гри «Життя», які складно взаємодіятимуть. При цьому «Критери» допускають складні космічні кораблі та осцилятори з нескінченним числом різних періодів.^[6]

Відомо кілька загальних методів побудови оборотних клітинних автоматів.

Блоковий клітинний автомат — клітинний автомат, комірки якого поділено на рівні блоки, а функція переходу застосовується до кожного блоку окремо. Зазвичай такий автомат по черзі використовує кілька розбиттів на блоки.^[7] Типовим прикладом такої схеми є окіл Марґолуса, в якому комірки квадратної ґратки поділено на блоки 2×2 вертикальними та горизонтальними прямими, а після кожного кроку поділ на блоки зсувається на одну комірку по горизонталі та вертикалі; завдяки цьому, всі чотири комірки будь-якого блоку на наступному кроці опиняються в різних блоках.^[8] «Критери», розглянуті вище, використовують окіл Марґолуса.

Щоб блоковий клітинний автомат був оборотним, необхідно і достатньо оборотності функції переходу на кожному блоці, що уможливлює перевірку оборотності блокового клітинного автомата за допомогою повного перебору. Обернений клітинний автомат у такому разі теж є блоковим із такою самою структурою розбиття на блоки, але оберненою функцією переходу.^[7]

Будь-який ${\displaystyle d}$-вимірний клітинний автомат можна вкласти в ${\displaystyle (d+1)}$-вимірний оборотний: в цьому разі кожен стан нового автомата зберігає всю історію еволюції старого. Використовуючи це вкладення, Тоффолі показав, що багато властивостей необоротних клітинних автоматів переносяться на оборотні, наприклад, вони можуть бути повними за Тюрінгом.^[9]

Збільшення розмірності в такій побудові не випадкове: за деяких слабких обмежень (на зразок інваріантності вкладення відносно паралельних перенесень) доведено, що будь-яке вкладення клітинного автомата з «едемським садом», тобто конфігурацією без попередників, у оборотний клітинний автомат має збільшувати розмірність.^[10]

Проте, за наявності станів спокою (англ. quiescent states), тобто станів, які не змінюються за умови, що сусідні стани також не змінюються^[як?], можливе моделювання кінцевої конфігурації клітинного автомата в блоковому оборотному клітинному автоматі тієї ж розмірності.^[11] Інформація, яка мала б бути втрачена на наступному кроці, натомість зберігається в нескінченній ділянці з клітин, які перебувають у стані спокою. В такому разі час, необхідний для моделювання частини конфігурації, пропорційний її обсягу. Тим не менш, така побудова дає змогу довести існування оборотного одновимірного клітинного автомата, повного за Тюрінгом.^[12]

• Скінченний автомат
• Фронтальний клітинний автомат
• Метод рухливих клітинних автоматів
• Елементарні клітинні автомати