Блочный клеточный автомат

Блочный клеточный автомат — класс клеточных автоматов, в которых решётка разбита на блоки, а функция перехода применяется к каждому блоку по отдельности. Блочные клеточные автоматы полезны для моделирования физических явлений, поскольку часто несложно выбрать функции перехода так, чтобы получившийся клеточный автомат был обратим и подчинялся выбранным законам сохранения.^[1]

Определение

Клеточный автомат — это регулярная решётка из ячеек, состояние каждой из которых берётся из конечного множества состояний, и функция перехода, необходимая для обновления состояний ячеек, исходя из состояний её соседей. Он называется блочным, если решётка разбита на равные непересекающиеся блоки и функция перехода использует в качестве окрестности каждой ячейки её блок. При этом автомат должен иметь некоторое конечное число разбиений на блоки, используемых поочерёдно: например, одно разбиение может сдвигаться в некотором направлении.^[1][2]

Таким образом, во время каждого шага автомата ко всем ячейкам одновременно применяется функция перехода, которая меняет каждый блок независимо от остальных, потом разбиение меняется на следующее и шаг повторяется. Это позволяет производить нетривиальные вычисления, используя достаточно простые функции перехода.

Примеры

Окрестность Марголуса для блочных клеточных автоматов. Правило преобразования по очереди действует на блоки 2 × 2, ограниченные голубыми линиями, и блоки 2 × 2, ограниченные пунктирными красными линиями.

Окрестность Марголуса

Простейшим примером такой схемы является окрестность Марголуса, в которой ячейки квадратной решётки поделены на блоки 2 × 2 вертикальными и горизонтальными прямыми, а после каждого шага разделение на блоки сдвигается на одну ячейку по горизонтали и вертикали; таким образом, все четыре ячейки любого блока оказываются в разных блоках на следующем шаге.^[3] Эта окрестность названа в честь Нормана Марголуса^[англ.] (англ. Norman Margolus), одного из первых исследователей блочных клеточных автоматов.^[1]

Криттеры

Основная статья: Криттеры

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