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

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

Определение

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

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

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

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

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

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

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

Примечания
  1. Schiff, Joel L. (2008), 4.2.1 Partitioning Cellular Automata, Cellular Automata: A Discrete View of the World, Wiley, с. 115–116
  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.
  4. Toffoli & Margolus (1987), section 12.8.2, «Critters», pp. 132—134; Margolus (1999); Marotta (2005).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.