Блочный клеточный автомат
Блочный клеточный автомат — класс клеточных автоматов, в которых решётка разбита на блоки, а функция перехода применяется к каждому блоку по отдельности. Блочные клеточные автоматы полезны для моделирования физических явлений, поскольку часто несложно выбрать функции перехода так, чтобы получившийся клеточный автомат был обратим и подчинялся выбранным законам сохранения.[1]
Определение[править | править код]
Клеточный автомат — это регулярная решётка из ячеек, состояние каждой из которых берётся из конечного множества состояний, и функция перехода, необходимая для обновления состояний ячеек, исходя из состояний её соседей. Он называется блочным, если решётка разбита на равные непересекающиеся блоки и функция перехода использует в качестве окрестности каждой ячейки её блок. При этом автомат должен иметь некоторое конечное число разбиений на блоки, используемых поочерёдно: например, одно разбиение может сдвигаться в некотором направлении.[1][2]
Таким образом, во время каждого шага автомата ко всем ячейкам одновременно применяется функция перехода, которая меняет каждый блок независимо от остальных, потом разбиение меняется на следующее и шаг повторяется. Это позволяет производить нетривиальные вычисления, используя достаточно простые функции перехода.
Примеры[править | править код]
Окрестность Марголуса[править | править код]
Простейшим примером такой схемы является окрестность Марголуса, в которой ячейки квадратной решётки поделены на блоки 2 × 2 вертикальными и горизонтальными прямыми, а после каждого шага разделение на блоки сдвигается на одну ячейку по горизонтали и вертикали; таким образом, все четыре ячейки любого блока оказываются в разных блоках на следующем шаге.[3] Эта окрестность названа в честь Нормана Марголуса[англ.] (англ. Norman Margolus), одного из первых исследователей блочных клеточных автоматов.[1]
Криттеры[править | править код]
Примером блочного клеточного автомата, использующим окрестность Марголуса, являются «Криттеры». Функция перехода «Криттеров» меняет состояние каждой ячейки на противоположное, если число живых ячеек в блоке не равняется двум, и вращает на 180° блок целиком, если это число равняется трём. Поскольку число живых ячеек меняется на число мёртвых, а функции перехода при каждом значении числа ячеек обратимы, такой клеточный автомат обратим на каждом блоке, а потому обратим в целом.[4] Тем не менее, он проявляет сложное динамическое поведение, схожее с игрой «Жизнь» Конвея; в частности, он полон по Тьюрингу, см. подробности в соответствующей статье.
Примечания[править | править код]
- ↑ 1 2 3 Schiff, Joel L. (2008), "4.2.1 Partitioning Cellular Automata", Cellular Automata: A Discrete View of the World, Wiley, pp. 115—116
- ↑ Toffoli, Tommaso; Margolus, Norman (1987), "II.12 The Margolus neighborhood", Cellular Automata Machines: A New Environment for Modeling, MIT Press, pp. 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).