Циклический клеточный автомат

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

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

Правила

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

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

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

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

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

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

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

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

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

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

Ссылки

• Белицкий, Владимир; Феррари, Пабло А. (1995). «Баллистическая аннигиляция и детерминированный рост поверхности». Журнал статистической физики . 80 (3–4): 517–543. Бибкод : 1995JSP....80..517B . дои : 10.1007/BF02178546 .
• Бунимович Л.А.; Трубецкой, С.Е. (1994). «Ротаторы, периодичность и отсутствие диффузии в циклических клеточных автоматах». Журнал статистической физики . 74 (1–2): 1–10. Бибкод : 1994JSP....74....1B . дои : 10.1007/BF02186804 .
• Дьюдни, АК (1989). «Компьютерные развлечения: клеточная вселенная мусора, капель, дефектов и демонов» . Scientific American (август): 102–105.
• Фиш, Р. (1990a). «Одномерный циклический клеточный автомат: система с детерминированной динамикой, которая имитирует взаимодействующую систему частиц со стохастической динамикой». Журнал теоретической вероятности . 3 (2): 311–338. дои : 10.1007/BF01045164 .
• Фиш, Р. (1990b). «Циклические клеточные автоматы и связанные с ними процессы». Физика Д. 45 (1–3): 19–25. Бибкод : 1990PhyD...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 .
• Фиш, Р.; Гравнер, Дж.; Гриффит, Д. (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 . Бибкод : 2005nlin......7067R .
• Стейф, Джеффри Э. (1995). «Два применения перколяции к клеточным автоматам». Журнал статистической физики . 78 (5–6): 1325–1335. Бибкод : 1995JSP....78.1325S . дои : 10.1007/BF02180134 .