Циклический клеточный автомат - Cyclic cellular automaton

Одномерный циклический клеточный автомат с п = 4, выполнить 300 шагов из случайной начальной конфигурации.

А циклический клеточный автомат это своего рода клеточный автомат правило, разработанное Дэвид Гриффит и изучен несколькими другими исследователями клеточных автоматов. В этой системе каждая ячейка остается неизменной до тех пор, пока в какой-то соседней ячейке не будет модульный значение ровно на одну единицу больше, чем у самой ячейки, и в этот момент она копирует значение своего соседа. Одномерные циклические клеточные автоматы можно интерпретировать как системы взаимодействующих частиц, в то время как циклические клеточные автоматы в более высоких измерениях демонстрируют сложное спиралевидное поведение.

Правила

Как и любой клеточный автомат, циклический клеточный автомат состоит из регулярной сетки ячеек в одном или нескольких измерениях. Клетки могут принимать любой из государства, начиная от к . Первое поколение начинается со случайных состояний в каждой из ячеек. В каждом последующем поколении, если у ячейки есть соседняя ячейка, значение которой является преемником значения ячейки, ячейка «потребляется» и принимает следующее значение. (Обратите внимание, что является преемником ; смотрите также модульная арифметика.) Более общие формы этого типа правил также включают порог параметр, и разрешить использование ячейки только в том случае, если количество соседей со значением преемника превышает этот порог.

Одно измерение

Одномерный циклический клеточный автомат широко изучался Робертом Фишем, учеником Гриффита.[1]Начиная со случайной конфигурации с п = 3 или п = 4, этот тип правила может создать паттерн, который при представлении в виде пространственно-временной диаграммы показывает растущие треугольники значений, конкурирующих за более крупные области сетки.

Границы между этими областями можно рассматривать как движущиеся частицы, которые сталкиваются и взаимодействуют друг с другом. В циклическом клеточном автомате с тремя состояниями граница между областями со значениями я и я + 1 (мод п) можно рассматривать как частицу, которая движется либо влево, либо вправо в зависимости от порядка областей; когда частица, движущаяся влево, сталкивается с частицей, движущейся вправо, они уничтожать друг друга, оставляя на две частицы меньше в системе. Этот тип баллистическая аннигиляция процесс происходит в нескольких других клеточных автоматах и ​​связанных с ними системах, включая Правило 184, клеточный автомат, используемый для моделирования транспортный поток.[2]

в п = 4 автомата, происходят те же два типа частиц и одна и та же реакция аннигиляции. Кроме того, граница между областями со значениями я и я + 2 (мод п) можно рассматривать как третий тип частиц, который остается неподвижным. Столкновение движущейся и неподвижной частицы приводит к тому, что одна движущаяся частица движется в противоположном направлении.

Однако для п ≥ 5 случайные начальные конфигурации имеют тенденцию к быстрой стабилизации, а не к формированию какой-либо нетривиальной дальнодействующей динамики. Гриффит прозвал эту дихотомию между динамикой частиц дальнего действия п = 3 и п = 4 с одной стороны, и статическое поведение п ≥ 5 автоматов, с другой стороны, «дилемма Боба» после Боба Фиша.[3]

Два или более измерения

Двумерный циклический клеточный автомат с п = 16, для 1300 шагов, начиная со случайной начальной конфигурации.

В двух измерениях, без порога и район фон Неймана или же Окрестности Мура, этот клеточный автомат последовательно генерирует три основных типа паттернов из случайных начальных условий на достаточно больших сетках, независимо от п.[4] Сначала поле чисто случайное. По мере того, как ячейки потребляют своих соседей и попадают в диапазон, который будет потреблен ячейками более высокого ранга, автомат переходит к фазе потребления, где есть блоки цвета, продвигающиеся против оставшихся блоков случайности. В дальнейшем развитии важны объекты, называемые демонами, которые представляют собой циклы соседних ячеек, содержащих по одной ячейке каждого состояния в циклическом порядке; эти циклы непрерывно вращаются и генерируют волны, которые распространяются в спираль узор сосредоточен в клетках демона. На третьей стадии, стадии демона, преобладают эти циклы. Демоны с более короткими циклами потребляют демонов с более длинными циклами, пока почти наверняка, каждая клетка автомата со временем входит в повторяющийся цикл состояний, где период повторения либо п или (для автоматов с п странный и район фон Неймана) п + 1. То же самое в конечном итоге периодическое поведение происходит и в более высоких измерениях. Небольшие конструкции также могут быть построены с любым четным периодом между п и 3п/ 2. Объединяя эти структуры, можно строить конфигурации с глобальным суперполиномиальным периодом.[5]

Для больших окрестностей аналогичное спиралевидное поведение происходит для низких порогов, но для достаточно высоких порогов автомат стабилизируется в блоке цветовой стадии, не образуя спиралей. При промежуточных значениях порога может образоваться сложное сочетание цветовых блоков и частичных спиралей, называемое турбулентностью.[6] При соответствующем выборе количества состояний и размера окрестности спиральные узоры, формируемые этим автоматом, могут быть похожи на спиральные узоры Реакция Белоусова – Жаботинского в химии или других системах автоволны, хотя другие клеточные автоматы более точно моделируют возбудимая среда что приводит к этой реакции.

Примечания

  1. ^ Фиш (1990a, 1990b, 1992).
  2. ^ Белицкий и Феррари (2005).
  3. ^ Дилемма Боба. Рецепт 29 в Primordial Soup Kitchen Дэвида Гриффита.
  4. ^ Бунимович и Трубецкой (1994); Дьюдни (1989); Фиш, Гравнер и Гриффит (1992); Шализи и Шализи (2003); Steif (1995).
  5. ^ Матамала и Морено (2004)
  6. ^ Турбулентное равновесие в циклическом клеточном автомате.. Рецепт 6 в David Griffeath's Первобытная суповая кухня.

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

  • Белицкий, Владимир; Феррари, Пабло А. (1995). «Баллистическая аннигиляция и детерминированный рост поверхности». Журнал статистической физики. 80 (3–4): 517–543. Bibcode:1995JSP .... 80..517B. Дои:10.1007 / BF02178546.
  • Бунимович Л. А .; Трубецкой, С. Э. (1994). «Ротаторы, периодичность и отсутствие диффузии в циклических клеточных автоматах». Журнал статистической физики. 74 (1–2): 1–10. Bibcode:1994JSP .... 74 .... 1B. Дои:10.1007 / BF02186804.
  • Дьюдни, А.К. (1989). «Компьютерные развлечения: клеточная вселенная мусора, капель, дефектов и демонов». Scientific American (Август): 102–105.
  • Фиш, Р. (1990а). «Одномерный циклический клеточный автомат: система с детерминированной динамикой, которая имитирует систему взаимодействующих частиц со стохастической динамикой». Журнал теоретической вероятности. 3 (2): 311–338. Дои:10.1007 / BF01045164.
  • Фиш, Р. (1990b). «Циклические клеточные автоматы и связанные с ними процессы». Physica D. 45 (1–3): 19–25. Bibcode:1990 ФИД ... 45 ... 19F. Дои:10.1016 / 0167-2789 (90) 90170-Т. Перепечатано в Гутовиц, Говард А., изд. (1991). Клеточные автоматы: теория и эксперимент. MIT Press / Северная Голландия. С. 19–25. ISBN  0-262-57086-6.
  • Фиш Р. (1992). «Кластеризация в одномерном трехцветном циклическом клеточном автомате». Анналы вероятности. 20 (3): 1528–1548. Дои:10.1214 / aop / 1176989705.
  • Fisch, R .; Gravner, J .; Гриффит, Д. (1991). «Масштабирование порогового диапазона возбудимых клеточных автоматов». Статистика и вычисления. 1: 23–39. arXiv:patt-sol / 9304001. Дои:10.1007 / BF01890834.
  • Матамала, Мартин; Морено, Эдуардо (2004). «Динамика циклических автоматов над Z ^ 2». Теоретическая информатика. 322 (2): 369–381. Дои:10.1016 / j.tcs.2004.03.018. HDL:10533/175114.
  • Шализи, Косма Рохилла; Шализи, Кристина Лиза (2003). «Количественная оценка самоорганизации в циклических клеточных автоматах». В лутце Шимански-Гейера; Дерек Эбботт; Александр Нейман; Кристиан Ван ден Брок (ред.). Шум в сложных системах и стохастическая динамика. Беллингхэм, Вашингтон: SPIE. С. 108–117. arXiv:nlin / 0507067. Bibcode:2005nlin ...... 7067R.
  • Steif, Джеффри Э. (1995). «Два приложения перколяции к клеточным автоматам». Журнал статистической физики. 78 (5–6): 1325–1335. Bibcode:1995JSP .... 78.1325S. Дои:10.1007 / BF02180134.