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

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

Правила [ править ]

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

Одно измерение [ править ]

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

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

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

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

Два или более измерения [ править ]

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

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

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

Примечания [ править ]

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

Ссылки [ править ]

  • Белицкий, Владимир; Феррари, Пабло А. (1995). «Баллистическая аннигиляция и детерминированный рост поверхности». Журнал статистической физики . 80 (3–4): 517–543. Bibcode : 1995JSP .... 80..517B . DOI : 10.1007 / BF02178546 .
  • Бунимович Л.А.; Трубецкой, С.Е. (1994). «Ротаторы, периодичность и отсутствие диффузии в циклических клеточных автоматах». Журнал статистической физики . 74 (1–2): 1–10. Bibcode : 1994JSP .... 74 .... 1B . DOI : 10.1007 / BF02186804 .
  • Дьюдни, АК (1989). «Компьютерные воссоздания: клеточная вселенная обломков, капель, дефектов и демонов» . Scientific American (август): 102–105.
  • Фиш, Р. (1990а). «Одномерный циклический клеточный автомат: система с детерминированной динамикой, которая имитирует систему взаимодействующих частиц со стохастической динамикой». Журнал теоретической вероятности . 3 (2): 311–338. DOI : 10.1007 / BF01045164 .
  • Фиш, Р. (1990b). «Циклические клеточные автоматы и связанные с ними процессы». Physica D . 45 (1–3): 19–25. Bibcode : 1990PhyD ... 45 ... 19F . DOI : 10.1016 / 0167-2789 (90) 90170-T .Перепечатано в Gutowitz, Howard A., ed. (1991). Клеточные автоматы: теория и эксперимент . MIT Press / Северная Голландия. С. 19–25. ISBN 0-262-57086-6.
  • Фиш Р. (1992). «Кластеризация в одномерном трехцветном циклическом клеточном автомате» . Анналы вероятности . 20 (3): 1528–1548. DOI : 10.1214 / AOP / 1176989705 .
  • Fisch, R .; Gravner, J .; Гриффит, Д. (1991). «Масштабирование порогового диапазона возбудимых клеточных автоматов». Статистика и вычисления . 1 : 23–39. arXiv : patt-sol / 9304001 . DOI : 10.1007 / BF01890834 .
  • Матамала, Мартин; Морено, Эдуардо (2004). «Динамика циклических автоматов над Z ^ 2». Теоретическая информатика . 322 (2): 369–381. DOI : 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 . DOI : 10.1007 / BF02180134 .