Введение
Циклический клеточный автомат - это своеобразное правило клеточного автомата, разработанное Дэвидом Гриффитом и изученное несколькими другими исследователями клеточного автомата. В этой системе каждая клетка остается неизменной до тех пор, пока какая-то соседняя клетка не имеет модульное значение, ровно на одну единицу большее, чем у самой клетки, и в этот момент она копирует значение своего соседа. Одномерные циклические клеточные автоматы могут интерпретироваться как системы взаимодействующих частиц, в то время как циклические клеточные автоматы в более высоких измерениях демонстрируют сложное спиральное поведение.
Правила
Как и любой клеточный автомат, циклический клеточный автомат состоит из регулярной сетки клеток в одном или нескольких измерениях. Клетки могут принимать любые состояния, начиная с первого поколения, начинается с случайных состояний в каждой из клеток. В каждом последующем поколении, если у клетки есть соседняя клетка, значение которой является преемником значения клетки, клетка "потребляется" и принимает следующее значение. (Обратите внимание, что это преемник; см. также модульную арифметику.) Более общие формы этого типа правила также включают пороговый параметр и позволяют использовать ячейку только тогда, когда количество соседей с преемником превышает этот порог.
Одно измерение
Одномерный циклический клеточный автомат был тщательно изучен Робертом Фишем, учеником Гриффита. Начиная с случайной конфигурации с 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 с другой стороны "дилеммой Боба" в честь Боба Фиша.