Блоковий клітинний автомат

Бло́ковий кліти́нний автома́т — клас клітинних автоматів, у яких ґратку розбито на блоки, а функція переходу застосовується до кожного блоку окремо. Блокові клітинні автомати корисні для моделювання фізичних явищ, оскільки часто нескладно вибрати функції переходу так, щоб клітинний автомат був оборотним і підкорявся вибраним законам збереження.^[1]

Визначення

Клітинний автомат — це регулярна ґратка з комірок, стан кожної з яких береться зі скінченної множини станів, і функція переходу, необхідна для оновлення станів комірок, виходячи зі станів їхніх сусідів. Його називають блоковим, якщо ґратку розбито на рівні блоки, що не перетинаються, і функція переходу використовує як окіл кожної комірки її блок. Такий автомат повинен мати певну скінченну кількість розбиттів на блоки, що використовуються почергово: наприклад, одне розбиття може зсуватися в певному напрямку.^[1]^[2]

Таким чином, під час кожного кроку автомата до всіх комірок одночасно застосовується функція переходу, яка змінює кожен блок незалежно від інших, потім розбиття змінюється наступним і повторюється крок. Це дозволяє виконувати нетривіальні обчислення, використовуючи достатньо прості функції переходу.

Приклади

Окіл Марґолуса

Найпростішим прикладом такої схеми є околиці Марґолуса, в якому комірки квадратної ґратки поділено на блоки 2×2 вертикальними та горизонтальними прямими, а після кожного кроку поділ на блоки зсувається на одну комірку по горизонталі та вертикалі; таким чином, всі чотири комірки будь-якого блоку опиняються на наступному кроці в різних блоках.^[3] Цей окіл названо на честь Нормана Марґолуса^[en] (англ. Norman Margolus), одного з перших дослідників блокових клітинних автоматів.^[1]

Критери

Докладніше: Критери

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

Примітки

↑ ^а ^б ^в Schiff, Joel L. (2008), 4.2.1 Partitioning Cellular Automata, Cellular Automata: A Discrete View of the World, Wiley, с. 115—116
↑ Toffoli, Tommaso; Margolus, Norman (1987), II.12 The Margolus neighborhood, Cellular Automata Machines: A New Environment for Modeling, MIT Press, с. 119—138
↑ Toffoli та Margolus, (1987), Chapter 12, «The Margolus Neighborhood», pp. 119—138.
↑ Toffoli та Margolus, (1987), section 12.8.2, «Critters», pp. 132—134; Margolus, (1999); Marotta, (2005).

[schiff-1] а ^б ^в Schiff, Joel L. (2008), 4.2.1 Partitioning Cellular Automata, Cellular Automata: A Discrete View of the World, Wiley, с. 115—116

[tm-2] Toffoli, Tommaso; Margolus, Norman (1987), II.12 The Margolus neighborhood, Cellular Automata Machines: A New Environment for Modeling, MIT Press, с. 119—138

[3] Toffoli та Margolus, (1987), Chapter 12, «The Margolus Neighborhood», pp. 119—138.

[critters-4] Toffoli та Margolus, (1987), section 12.8.2, «Critters», pp. 132—134; Margolus, (1999); Marotta, (2005).

[1]

[2]

[3]

[4]