Блок клеточного автомата - Block cellular automaton

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

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

Определение

Блочный клеточный автомат состоит из следующих компонентов:[1][2]

  • Обычный решетка ячеек
  • Конечное множество состояний, в которых может находиться каждая ячейка.
  • Разделение ячеек на униформу мозаика в котором каждая плитка перегородки имеет одинаковый размер и форму
  • Правило смещения раздела после каждого временного шага
  • Правило перехода, функция, которая принимает в качестве входных данных назначение состояний для ячеек в одной плитке и производит в качестве выходных данных другое назначение состояний для тех же ячеек.

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

Окрестности

Самая простая схема разбиения, вероятно, Район Марголус, названный в честь Норман Марголус, который первым изучил блочно-клеточные автоматы, используя эту структуру соседства. В микрорайоне Марголус решетка делится на 2-ячейковые блоки (или 2 × 2 квадраты в двух измерениях, или 2 × 2 × 2 кубы в трех измерениях и т. д.), которые сдвигаются на одну ячейку (по каждому измерению) на разных временных шагах.[1][2][3]

Тесно родственная техника, созданная К. Морита и М. Харао.[4] состоит в разбиении каждой ячейки на конечное число частей, каждая из которых посвящена некоторому соседу. Эволюция происходит путем обмена соответствующими частями между соседями и последующего применения к каждой ячейке чисто локального преобразования. зависит только от состояния ячейки (а не от состояний ее соседей). При такой схеме построения клеточный автомат гарантированно обратим, если локальное преобразование сам по себе биекция. Этот метод можно рассматривать как блочный клеточный автомат на более тонкой решетке ячеек, образованной частями каждой более крупной ячейки; блоки этой более тонкой решетки чередуются между наборами частей в одной большой ячейке и наборами частей в соседних ячейках, которые разделяют части друг с другом.

Обратимость и сохранение

Если правило развития каждого блока обратимый, весь автомат тоже будет. Более того, в этом случае обращенное во времени поведение автомата можно также описать как блочный клеточный автомат с той же блочной структурой и правилом перехода, которое инвертирует исходное правило автомата в каждом блоке. Верно и обратное: если блоки не обратимы по отдельности, глобальная эволюция не может быть обратимой: если две разные конфигурации Икс и у блока приводят к тому же состоянию результата z, затем глобальная конфигурация с Икс в одном блоке будет неотличима после одного шага от конфигурации, в которой Икс заменяется на у. То есть клеточный автомат глобально обратим тогда и только тогда, когда он обратим на уровне блоков.[5]

Простота конструирования обратимых блочных клеточных автоматов и тестирования блочных клеточных автоматов на обратимость резко контрастирует с клеточными автоматами с другими неблочными структурами соседства, для которых это неразрешимый является ли автомат обратимым и для которого обратная динамика может потребовать гораздо больших окрестностей, чем прямая динамика.[6] Любой обратимый клеточный автомат может быть смоделирован обратимым блочным клеточным автоматом с большим числом состояний; однако из-за неразрешимости обратимости для неблочных клеточных автоматов не существует вычислимой границы радиуса областей в неблочном автомате, которые соответствуют блокам в моделировании, и трансляции из неблочного правила в правило блока также не вычислимо.[7]

Блочно-клеточные автоматы также представляют собой удобный формализм для разработки правил, которые, помимо обратимости, реализуют законы сохранения таких как сохранение числа частиц, сохранение импульса и т. д. Например, если правило в каждом блоке сохраняет количество живых клеток в блоке, то глобальная эволюция автомата также сохранит то же число. Это свойство полезно в приложениях клеточных автоматов к физическому моделированию.[8]

Моделирование обычными клеточными автоматами

Как пишут Тоффоли и Марголус,[2] модель блочного клеточного автомата не вводит никакой дополнительной мощности по сравнению с обычным клеточным автоматом, который использует ту же структуру соседства на каждом временном шаге: любой блочный клеточный автомат может быть смоделирован на обычном клеточном автомате, используя большее количество состояний и большую окрестность. В частности, пусть два автомата используют одну и ту же решетку ячеек, но пусть каждое состояние обычного автомата определяет состояние блочного автомата, фазу его шаблона сдвига разделов и положение ячейки в его блоке. Например, в районе Марголуса это увеличило бы количество состояний в восемь раз: есть четыре возможных положения, которые ячейка может занять в своем 2 × 2 блок, и две фазы в перегородку. Кроме того, пусть окрестность обычного автомата представляет собой объединение блоков, содержащих данную клетку, в блочно-клеточном автомате. Затем с этой структурой соседства и состояний каждое обновление блочного автомата может быть смоделировано одним обновлением обычного клеточного автомата.

Приложения

Блочные клеточные автоматы обычно используются для реализации решеточные газы и другие квазифизические моделирование, благодаря простоте моделирования физических ограничений, таких как законы сохранения в этих системах.[1][8]Например, модель Марголуса может использоваться для моделирования модели решеточного газа HPP, в которой частицы движутся в двух перпендикулярных направлениях и разлетаются под прямым углом, когда сталкиваются друг с другом. В блочно-клеточном моделировании этой модели правило обновления перемещает каждую ячейку в ячейку, диагонально противоположную в своем блоке, за исключением случая, когда ячейка содержит две диагонально противоположные частицы, и в этом случае они заменяются дополнительной парой диагонально противоположных частиц. частицы. Таким образом, частицы движутся по диагонали и разлетаются в соответствии с моделью HPP.[2][9] Альтернативное правило, которое имитирует модель решеточного газа HPP с горизонтальным и вертикальным движением частиц, а не с диагональным движением, включает вращение содержимого каждого блока по часовой стрелке или против часовой стрелки в чередующихся фазах, за исключением случая, когда ячейка содержит два диагонально противоположных частиц, в этом случае он остается неизменным.[2]В любой из этих моделей импульс (сумма векторы скорости движущихся частиц) сохраняется, как и их количество, что является важным свойством для моделирования физических газов. Однако модели HPP несколько нереалистичны в качестве модели газовой динамики, потому что они имеют дополнительные нефизические правила сохранения: общий импульс внутри каждой линии движения, а также полный импульс всей системы, сохраняется. Более сложные модели, основанные на гексагональной сетке, позволяют избежать этой проблемы.[9]

Эти автоматы также могут быть использованы для моделирования движения зерен песок в кучах песка и песочные часы. В этом приложении можно использовать соседство Марголуса с правилом обновления, которое сохраняет количество зерен в каждом 2 × 2 block, но при этом каждое зерно перемещается как можно дальше вниз в пределах своего блока. Если блок включает в себя два зерна, которые уложены вертикально друг на друга, функция перехода автомата заменяет его блоком, в котором зерна расположены бок о бок, в результате чего высокие кучи песка опрокидываются и разлетаются. Эта модель необратима, но по-прежнему подчиняется закону сохранения числа частиц.[10] Модифицированное правило, использующее одну и ту же окрестность, но перемещая частицы в сторону, насколько это возможно, а также вниз, позволяет смоделированным кучам песка распространяться, даже если они не очень крутые.[11] Также возможны более сложные модели песчаных куч с клеточными автоматами, включающие такие явления, как перенос ветра и трение.[10]

Первоначальное приложение Марголуса для модели блочного клеточного автомата состояло в моделировании бильярдный шар обратимого вычисления, в котором Логическая логика сигналы моделируются движущимися частицами, а логические элементы моделируются упругие столкновения этих частиц. Например, можно выполнять вычисления бильярдного шара в двумерной модели Марголуса, с двумя состояниями на ячейку и с количеством живых клеток, сохраняемых в ходе эволюции модели. В правиле «BBM», которое имитирует модель бильярдного шара, сигналы состоят из отдельных живых клеток, движущихся по диагонали. Чтобы выполнить это движение, функция перехода блока заменяет блок, содержащий одну активную ячейку, другим блоком, в котором ячейка была перемещена в противоположный угол блока. Точно так же упругие столкновения могут выполняться функцией перехода блока, которая заменяет две диагонально противоположные живые клетки двумя другими ячейками блока. Во всех других конфигурациях блока функция перехода блока не изменяет его состояние. В этой модели 2 × 4 прямоугольники живых клеток (тщательно выровненные по отношению к перегородке) остаются стабильными и могут использоваться в качестве зеркал, направляющих пути движущихся частиц. Например, на иллюстрации района Марголус показаны четыре частицы и зеркало; если на следующем шаге используется синяя перегородка, то две частицы движутся к зеркалу, в то время как две другие собираются столкнуться, тогда как если на следующем шаге используется красная перегородка, то две частицы удаляются от зеркала, а две другие просто столкнулись и будут отдаляться друг от друга.[3][5][12]

Дополнительные правила

Согласно правилу Critters, планеры избегают центрального случайного семени, мимо обломков более ранних падений планеров.

Тоффоли и Марголус[2] предлагают еще два обратимых правила для окрестности Марголуса с ячейками с двумя состояниями, которые, хотя и не мотивированы физическими соображениями, приводят к интересной динамике.

Critters

Основная статья: Существа (клеточный автомат)

В правиле «Critters» функция перехода меняет состояние каждой ячейки в блоке, за исключением блока с двумя живыми ячейками, который остается неизменным. Кроме того, блоки с тремя живыми клетками подвергаются повороту на 180 градусов, а также изменению состояния.[2] Это обратимое правило, и оно подчиняется законам сохранения числа частиц (считая частицу живой клеткой в ​​четных фазах и мертвой клеткой в ​​нечетных фазах) и четности числа частиц вдоль диагональных линий.[12] Поскольку это обратимо, начальные состояния, в которых все клетки принимают случайно выбранные состояния, остаются неструктурированными на протяжении всей своей эволюции. Однако, если начать с меньшего поля случайных ячеек, сосредоточенных в большей области мертвых клеток, это правило приводит к сложной динамике, аналогичной динамике в Игра жизни Конвея в котором много маленьких узоров, похожих на планер сбежать из центральной случайной области и взаимодействовать друг с другом.[2][12] В отличие от планеров в Life, обратимость и сохранение частиц вместе означают, что, когда планеры в Critters сталкиваются вместе, по крайней мере один должен сбежать, и часто эти аварии позволяют обоим приближающимся планерам воссоздать себя на разных исходящих треках. Посредством таких столкновений это правило может также моделировать вычислительную модель бильярдного шара, хотя и более сложным образом, чем правило BBM.[12] Правило Critters также может поддерживать более сложные космические корабли различной скорости, а также генераторы с бесконечным множеством разных периодов.[13]

Трон

Прямолинейные формы, созданные по правилу Трона.

В правиле «Tron» функция перехода оставляет каждый блок неизменным, за исключением случаев, когда все четыре его ячейки имеют одно и то же состояние, и в этом случае все их состояния меняются местами. Выполнение этого правила из начальных условий в форме прямоугольника живых ячеек или из аналогичных простых форм с прямыми краями приводит к сложным прямолинейным образцам. Тоффоли и Марголус также предполагают, что это правило можно использовать для реализации правила локальной синхронизации, которое позволяет моделировать любой блочный клеточный автомат района Марголуса с использованием асинхронный клеточный автомат. В этом моделировании каждая ячейка асинхронного автомата хранит как состояние моделируемого автомата, так и второй бит, представляющий паритет метки времени для этой ячейки; следовательно, получившийся асинхронный автомат имеет в два раза больше состояний, чем автомат, который он моделирует. Временные метки должны отличаться не более чем на одну между соседними ячейками, и любой блок из четырех ячеек, все метки времени которых имеют правильную четность, может быть обновлен в соответствии с правилом блока, которое моделируется. Когда выполняется обновление этого типа, четности меток времени также должны обновляться в соответствии с правилом Tron, которое обязательно сохраняет ограничение на соседние метки времени. Выполняя локальные обновления таким образом, эволюция каждой ячейки в асинхронном автомате идентична ее эволюции в моделируемом синхронном блочном автомате.[2][14]

Первые три шага последовательности зубочисток и ее эмуляция блочным клеточным автоматом с окрестностью Марголуса

Смотрите также

Рекомендации

  1. ^ а б c d Шифф, Джоэл Л. (2008), "4.2.1 Разбиение клеточных автоматов", Клеточные автоматы: дискретный взгляд на мир, Wiley, стр. 115–116.
  2. ^ а б c d е ж грамм час я Тоффоли, Томмазо; Марголус, Норман (1987), «II.12 Окрестности Марголуса», Машины с клеточными автоматами: новая среда для моделирования, MIT Press, стр. 119–138.
  3. ^ а б Марголус, Н. (1984), "Физические модели вычислений", Physica D, 10: 81–95, Bibcode:1984 ФИД ... 10 ... 81M, Дои:10.1016/0167-2789(84)90252-5. Перепечатано в Вольфрам, Стивен, изд. (1986), Теория и приложения клеточных автоматов, Расширенная серия по сложным системам, 1, World Scientific, стр. 232–246.
  4. ^ Morita, K .; Харао, М. (1989), "Вычислительная универсальность одномерных обратимых (инъективных) клеточных автоматов", Сделки Институт инженеров электроники, информации и связи, E, 72: 758–762
  5. ^ а б Дюран-Лоз, Жером (2002), «Вычисления внутри модели бильярдного шара», в Адамацкий Андрей (ред.), Вычисления на основе коллизий, Springer-Verlag, стр. 135–160.
  6. ^ Кари, Яркко (1990), «Обратимость двумерных клеточных автоматов неразрешима», Physica D, 45: 379–385, Bibcode:1990 ФИД ... 45..379K, Дои:10.1016 / 0167-2789 (90) 90195-У
  7. ^ Кари, Яркко (1999), "О глубине схемы структурно обратимых клеточных автоматов", Fundamenta Informaticae, 38: 93–107; Дюран-Лоз, Жером (2001), «Представление обратимых клеточных автоматов с помощью обратимых блочных клеточных автоматов», Дискретная математика и теоретическая информатика, AA: 145–154, архивировано с оригинал на 2011-05-15
  8. ^ а б Вольфрам, Стивен (2002), Новый вид науки, Вольфрам Медиа, стр.459–464, ISBN  1-57955-008-8
  9. ^ а б «5.5.4 Решеточные газы», ​​дюйм Шифф (2008) С. 165–169.
  10. ^ а б Chopard, Bastien; Дроз, Майкл (1998), «2.2.6 Правило песчаной кучи», Моделирование физических систем клеточными автоматами, Cambridge University Press, стр. 42–46.
  11. ^ Груау, Фредерик; Тромп, Джон (2000), «Клеточная гравитация» (PDF), Письма параллельной обработки, 10 (4): 383–393, Дои:10.1142 / s0129626400000354, заархивировано из оригинал (PDF) на 2011-07-18
  12. ^ а б c d Марголус, Норман (1999), «Кристаллические вычисления», в Hey, Энтони Дж. Г. (ред.), Фейнман и вычисления, Perseus Books, стр. 267–305, arXiv:комп-газ / 9811002, Bibcode:1998comp.gas.11002M
  13. ^ Маротта, Себастьян М. (2005), «Жизнь в мире зверей», Revista Ciências Exatas e Naturais, 7 (1), заархивировано из оригинал на 2012-03-19
  14. ^ Охала, Лев; Пенттинен, Олли-Матти; Парвиайнен, Элина (2004), "Моделирование и анализ квантовых клеточных автоматов Margolus с использованием теоретико-сетевых методов", Приложения и теория сетей Петри 2004, Конспект лекций по информатике, 3099, Springer-Verlag, стр. 331–350, Дои:10.1007/978-3-540-27793-4_19

внешняя ссылка