Блочный клеточный автомат или разделяющий клеточный автомат — это особый вид клеточного автомата , в котором решетка ячеек разделена на неперекрывающиеся блоки (с разными разделами на разных временных шагах), а правило перехода применяется ко всему блоку за раз, а не к одной ячейке. Блочные клеточные автоматы полезны для моделирования физических величин, поскольку легко выбрать правила перехода, которые подчиняются физическим ограничениям, таким как обратимость и законы сохранения . [1]
Блочный клеточный автомат состоит из следующих компонентов: [1] [2]
На каждом временном шаге правило перехода применяется одновременно и синхронно ко всем плиткам в разделе. Затем раздел сдвигается, и та же операция повторяется на следующем временном шаге и т. д. Таким образом, как и в любом клеточном автомате, шаблон состояний ячеек со временем изменяется для выполнения некоторых нетривиальных вычислений или моделирования.
Простейшей схемой разбиения, вероятно, является окрестность Марголуса , названная в честь Нормана Марголуса , который впервые изучал блочные клеточные автоматы, используя эту структуру соседства. В окрестности Марголуса решетка разделена на 2 -клеточные блоки (или 2 × 2 квадрата в двух измерениях, или 2 × 2 × 2 куба в трех измерениях и т. д.), которые сдвинуты на одну ячейку (вдоль каждого измерения) на альтернативных временных шагах. [1] [2] [3]
Близкий метод, предложенный К. Морита и М. Харао [4], состоит в разбиении каждой клетки на конечное число частей, каждая из которых отводится некоторому соседу. Эволюция происходит путем обмена соответствующими частями между соседями и последующего применения к каждой клетке чисто локального преобразования, зависящего только от состояния клетки (а не от состояний ее соседей). При такой схеме построения клеточный автомат гарантированно обратим, если локальное преобразование само по себе является биекцией . Этот метод можно рассматривать как блочный клеточный автомат на более мелкой решетке клеток, образованной частями каждой более крупной клетки; блоки этой более мелкой решетки чередуются между наборами частей внутри одной большой клетки и наборами частей в соседних клетках, которые делят части друг с другом.
Пока правило развития каждого блока обратимо , весь автомат также будет обратимым. Более строго, в этом случае обращенное во времени поведение автомата также может быть описано как блочный клеточный автомат с той же блочной структурой и с правилом перехода, которое инвертирует правило исходного автомата внутри каждого блока. Обратное также верно: если блоки не являются индивидуально обратимыми, глобальная эволюция не может быть обратимой: если две различные конфигурации x и y блока приводят к одному и тому же конечному состоянию z , то глобальная конфигурация с x в одном блоке будет неотличима после одного шага от конфигурации, в которой x заменен на y . То есть клеточный автомат обратим глобально тогда и только тогда, когда он обратим на уровне блока. [5]
Легкость проектирования обратимых блочных клеточных автоматов и тестирования блочных клеточных автоматов на обратимость резко контрастирует с клеточными автоматами с другими неблочными соседними структурами, для которых невозможно решить, является ли автомат обратимым, и для которых обратная динамика может потребовать гораздо больших окрестностей, чем прямая динамика. [6] Любой обратимый клеточный автомат может быть смоделирован обратимым блочным клеточным автоматом с большим числом состояний; однако из-за неразрешимости обратимости для неблочных клеточных автоматов не существует вычислимой границы радиуса областей в неблочном автомате, которые соответствуют блокам в моделировании, и перевод из неблочного правила в блочное правило также невычислим. [7]
Блочные клеточные автоматы также являются удобным формализмом, в котором можно разрабатывать правила, которые, в дополнение к обратимости, реализуют законы сохранения, такие как сохранение числа частиц, сохранение импульса и т. д. Например, если правило внутри каждого блока сохраняет число живых клеток в блоке, то глобальная эволюция автомата также сохранит то же число. Это свойство полезно в приложениях клеточных автоматов к физическому моделированию. [8]
Как пишут Тоффоли и Марголус, [2] модель блочного клеточного автомата не вносит никакой дополнительной мощности по сравнению с обычным клеточным автоматом, который использует ту же структуру соседства на каждом временном шаге: любой блочный клеточный автомат может быть смоделирован на обычном клеточном автомате, используя больше состояний и большее соседство. В частности, пусть два автомата используют одну и ту же решетку ячеек, но пусть каждое состояние обычного автомата определяет состояние блочного автомата, фазу его шаблона сдвига разбиения и положение ячейки внутри ее блока. Например, с соседством Марголуса это увеличило бы число состояний в восемь раз: существует четыре возможных положения, которые ячейка может занять в своем блоке 2 × 2 , и две фазы для разбиения. Кроме того, пусть соседство обычного автомата будет объединением блоков, содержащих данную ячейку в блочном клеточном автомате. Затем с помощью этой структуры соседства и состояния каждое обновление блочного автомата можно смоделировать с помощью одного обновления обычного клеточного автомата.
Блочные клеточные автоматы обычно используются для реализации решеточных газов и других квазифизических симуляций из-за простоты моделирования физических ограничений, таких как законы сохранения в этих системах. [1] [8] Например, модель Марголуса может использоваться для моделирования модели решеточного газа HPP, в которой частицы движутся в двух перпендикулярных направлениях и рассеиваются под прямым углом при столкновении друг с другом. В блочной клеточной симуляции этой модели правило обновления перемещает каждую ячейку в ячейку, диагонально противоположную в ее блоке, за исключением случая, когда ячейка содержит две диагонально противоположные частицы, в этом случае они заменяются комплементарной парой диагонально противоположных частиц. Таким образом, частицы движутся по диагонали и рассеиваются в соответствии с моделью HPP. [2] [9] Альтернативное правило, которое моделирует модель решеточного газа HPP с горизонтальным и вертикальным движением частиц, а не с диагональным движением, включает вращение содержимого каждого блока по часовой стрелке или против часовой стрелки в чередующихся фазах, за исключением случая, когда ячейка содержит две диагонально противоположные частицы, в этом случае она остается неизменной. [2] В любой из этих моделей сохраняется импульс (сумма векторов скорости движущихся частиц), а также их число, что является существенным свойством для моделирования физических газов. Однако модели HPP несколько нереалистичны как модели газовой динамики, поскольку они имеют дополнительные нефизические правила сохранения: сохраняется полный импульс в пределах каждой линии движения, а также полный импульс всей системы. Более сложные модели, основанные на гексагональной сетке, избегают этой проблемы. [9]
Эти автоматы также могут использоваться для моделирования движения песчинок в кучах песка и песочных часах . В этом приложении можно использовать окрестность Марголуса с правилом обновления, которое сохраняет количество песчинок в каждом блоке 2 × 2 , но перемещает каждую песчинку как можно ниже в пределах своего блока. Если блок включает в себя две песчинки, которые уложены вертикально друг на друга, функция перехода автомата заменяет его блоком, в котором песчинки находятся рядом, что фактически позволяет высоким песчаным кучам опрокидываться и растекаться. Эта модель необратима, но она по-прежнему подчиняется закону сохранения количества частиц. [10] Модифицированное правило, использующее ту же окрестность, но перемещающее частицы вбок, насколько это возможно, а также вниз, позволяет моделируемым песчаным кучам растекаться, даже если они не очень крутые. [11] Также возможны более сложные модели песчаных куч на основе клеточного автомата, включающие такие явления, как перенос ветра и трение. [10]
Первоначальное применение Марголуса для модели блочного клеточного автомата состояло в моделировании модели обратимых вычислений бильярдного шара , в которой булевы логические сигналы моделируются движущимися частицами, а логические вентили моделируются упругими столкновениями этих частиц. Например, можно выполнять вычисления бильярдного шара в двумерной модели Марголуса с двумя состояниями на ячейку и с числом живых ячеек, сохраняемым эволюцией модели. В правиле «BBM», которое моделирует модель бильярдного шара таким образом, сигналы состоят из отдельных живых ячеек, движущихся по диагонали. Чтобы выполнить это движение, функция перехода блока заменяет блок, содержащий одну живую ячейку, другим блоком, в котором ячейка была перемещена в противоположный угол блока. Аналогично упругие столкновения могут быть выполнены функцией перехода блока, которая заменяет две диагонально противоположные живые ячейки двумя другими ячейками блока. Во всех других конфигурациях блока функция перехода блока не вносит изменений в его состояние. В этой модели прямоугольники 2 × 4 живых клеток (тщательно выровненные относительно перегородки) остаются стабильными и могут использоваться в качестве зеркал для направления траекторий движущихся частиц. Например, на иллюстрации окрестностей Марголуса показаны четыре частицы и зеркало; если на следующем шаге используется синяя перегородка, то две частицы движутся к зеркалу, а две другие собираются столкнуться, тогда как если на следующем шаге используется красная перегородка, то две частицы движутся от зеркала, а две другие только что столкнулись и будут разъезжаться друг от друга. [3] [5] [12]
Тоффоли и Марголус [2] предлагают еще два обратимых правила для окрестности Марголуса с ячейками с двумя состояниями, которые, хотя и не мотивированы физическими соображениями, приводят к интересной динамике.
В правиле «Critters» функция перехода меняет состояние каждой клетки в блоке, за исключением блока с ровно двумя живыми клетками, который остается неизменным. Кроме того, блоки с тремя живыми клетками подвергаются повороту на 180 градусов, а также изменению состояния. [2] Это обратимое правило, и оно подчиняется законам сохранения числа частиц (считая частицу живой клеткой в четных фазах и мертвой клеткой в нечетных фазах) и четности числа частиц вдоль диагональных линий. [12] Поскольку оно обратимо, начальные состояния, в которых все клетки принимают случайно выбранные состояния, остаются неструктурированными на протяжении всей своей эволюции. Однако, когда начинается с меньшего поля случайных клеток, центрированных в большей области мертвых клеток, это правило приводит к сложной динамике, похожей на динамику в игре Конвея «Жизнь» , в которой множество небольших узоров, похожих на планер жизни , покидают центральную случайную область и взаимодействуют друг с другом. [2] [12] В отличие от планеров в Life, обратимость и сохранение частиц вместе подразумевают, что когда планеры сталкиваются друг с другом в Critters, по крайней мере один должен спастись, и часто эти столкновения позволяют обоим входящим планерам восстанавливаться на разных исходящих траекториях. Посредством таких столкновений это правило также может имитировать модель бильярдного шара вычислений, хотя и более сложным способом, чем правило BBM. [12] Правило Critters также может поддерживать более сложные космические корабли с различными скоростями, а также осцилляторы с бесконечным количеством различных периодов. [13]
В правиле «Tron» функция перехода оставляет каждый блок неизменным, за исключением случаев, когда все четыре его ячейки имеют одинаковое состояние, в этом случае их состояния меняются на противоположные. Запуск этого правила из начальных условий в форме прямоугольника живых ячеек или из аналогичных простых прямолинейных форм приводит к сложным прямолинейным узорам. Тоффоли и Марголус также предполагают, что это правило можно использовать для реализации локального правила синхронизации, которое позволяет моделировать любой клеточный автомат блока соседства Марголуса с помощью асинхронного клеточного автомата . В этой симуляции каждая ячейка асинхронного автомата хранит как состояние для моделируемого автомата, так и второй бит, представляющий четность временной метки для этой ячейки; следовательно, полученный асинхронный автомат имеет вдвое больше состояний, чем автомат, который он моделирует. Временные метки ограничены тем, чтобы отличаться не более чем на единицу между соседними ячейками, и любой блок из четырех ячеек, все временные метки которых имеют правильную четность, может быть обновлен в соответствии с моделируемым правилом блока. Когда выполняется обновление этого типа, четности временных меток также должны обновляться в соответствии с правилом Tron, которое обязательно сохраняет ограничение на смежные временные метки. Выполняя локальные обновления таким образом, эволюция каждой ячейки в асинхронном автомате идентична ее эволюции в синхронном блочном автомате, который моделируется. [2] [14]
