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

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

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

Приклади

Окіл Марґолуса Найпростішим прикладом такої схеми є окіл Марґолуса, в якому комірки квадратної ґратки поділено на блоки 2×2 вертикальними та горизонтальними прямими, а після кожного кроку поділ на блоки зсувається на одну комірку по горизонталі та вертикалі; таким чином, всі чотири комірки будь-якого блоку опиняються на наступному кроці в різних блоках., Chapter 12, «The Margolus Neighborhood», pp. 119—138. Цей окіл названо на честь (), одного з перших дослідників блокових клітинних автоматів.

Критери

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

Примітки