Правило 184 — это одномерное бинарное правило клеточного автомата , примечательное решением проблемы большинства , а также способностью одновременно описывать несколько, казалось бы, совершенно разных систем частиц :
Кажущееся противоречие между этими описаниями разрешается различными способами связывания особенностей состояния автомата с частицами.
Название Правила 184 — это код Вольфрама , определяющий эволюцию его состояний. Самое раннее исследование Правила 184 было проведено Ли (1987) и Krug & Spohn (1988). В частности, Круг и Спон уже описывают все три типа систем частиц, моделируемых Правилом 184. [2]
Состояние автомата по Правилу 184 состоит из одномерного массива ячеек, каждая из которых содержит двоичное значение (0 или 1). На каждом этапе своей эволюции автомат «Правило 184» применяет следующее правило к каждой ячейке массива одновременно для всех ячеек, чтобы определить новое состояние ячейки: [3]
Запись в этой таблице определяет новое состояние каждой ячейки как функцию предыдущего состояния и предыдущих значений соседних ячеек с обеих сторон. Название этого правила, Rule 184, представляет собой код Wolfram , описывающий приведенную выше таблицу состояний: нижняя строка таблицы, 10111000, если рассматривать ее как двоичное число , равна десятичному числу 184 . [4]
Набор правил для Правила 184 также можно описать интуитивно несколькими способами:
Из описаний правил, приведенных выше, сразу можно увидеть два важных свойства его динамики. Во-первых, в Правиле 184 для любого конечного набора ячеек с периодическими граничными условиями количество единиц и количество нулей в шаблоне остается неизменным на протяжении всего развития шаблона. Правило 184 и его отражение — единственные нетривиальные [7] элементарные клеточные автоматы , обладающие этим свойством сохранения числа. [8] Аналогично, если плотность единиц четко определена для бесконечного массива ячеек, она остается инвариантной, пока автомат выполняет свои шаги. [9] И во-вторых, хотя правило 184 не симметрично относительно перестановки левого и правого, оно имеет другую симметрию: перестановка левого и правого местами и в то же время замена ролей символов 0 и 1 дает клеточный автомат с тем же самым правило обновления.
Шаблоны в Правиле 184 обычно быстро стабилизируются либо до шаблона, в котором состояния ячеек синхронно перемещаются на одну позицию влево на каждом шаге, либо до шаблона, который перемещается на одну позицию вправо на каждом шаге. В частности, если начальная плотность ячеек с состоянием 1 составляет менее 50%, паттерн стабилизируется в кластеры ячеек в состоянии 1, расположенные на расстоянии двух единиц друг от друга, причем кластеры разделены блоками ячеек в состоянии 0. Паттерны этого типа перемещаются. вправо. Если, с другой стороны, начальная плотность превышает 50%, паттерн стабилизируется в кластеры ячеек в состоянии 0, расположенные на расстоянии двух единиц друг от друга, причем кластеры разделены блоками ячеек в состоянии 1, и паттерны этого типа перемещаются. влево. Если плотность составляет точно 50%, исходный паттерн стабилизируется (более медленно) до паттерна, который эквивалентно можно рассматривать как движение либо влево, либо вправо на каждом шаге: чередующуюся последовательность 0 и 1. [10]
Проблема большинства — это проблема построения клеточного автомата, который при запуске на любом конечном наборе ячеек может вычислить значение, содержащееся в большинстве своих ячеек. В каком-то смысле Правило 184 решает эту проблему следующим образом. если правило 184 применяется к конечному набору ячеек с периодическими граничными условиями, с неравным количеством нулей и единиц, то каждая ячейка в конечном итоге бесконечно часто будет видеть два последовательных состояния значения большинства, но будет видеть два последовательных состояния меньшинства. значение только конечное число раз. [11] Проблема большинства не может быть решена идеально, если требуется, чтобы все ячейки в конечном итоге стабилизировались до состояния большинства [12], но решение по Правилу 184 позволяет избежать этого невозможного результата, ослабив критерий, по которому автомат распознает большинство.
Если интерпретировать каждую 1-клетку в Правиле 184 как содержащую частицу, эти частицы во многом ведут себя аналогично автомобилям, движущимся по одной полосе движения: они движутся вперед с постоянной скоростью, если перед ними есть открытое пространство, и в противном случае они останавливаются. Модели трафика, такие как Правило 184 и его обобщения, которые дискретизируют как пространство, так и время, обычно называются моделями скачкообразного перемещения частиц . [13] Хотя модель транспортного потока по Правилу 184 очень примитивна, она уже предсказывает некоторые знакомые возникающие особенности реального дорожного движения: группы свободно движущихся автомобилей, разделенные участками открытой дороги при слабом движении, и волны пробок с остановками. движение , когда оно тяжелое. [14]
Трудно определить первое использование Правила 184 для моделирования транспортных потоков, отчасти потому, что исследования в этой области были направлены не столько на достижение максимального уровня математической абстракции, сколько на правдоподобие: даже более ранние статьи по клеточным автоматам, основанные на Моделирование транспортных потоков обычно усложняет модель, чтобы более точно имитировать реальный трафик. Тем не менее, Правило 184 имеет основополагающее значение для моделирования трафика клеточными автоматами. Ван, Квонг и Хуэй (1998), например, утверждают, что «базовой моделью клеточного автомата, описывающей одномерную проблему транспортного потока, является правило 184». Нагель (1996) пишет: «Большая часть работ по использованию моделей CA для трафика основана на этой модели». Некоторые авторы описывают одномерные модели транспортных средств, движущихся с разными скоростями; такие модели вырождаются до правила 184 в случае односкоростного режима. [15] Gaylord & Nishidate (1996) распространяют действие Правила 184 на двухполосное движение по шоссе со сменой полос движения; их модель и Правило 184 имеют то общее свойство, что она симметрична при одновременном развороте левого-правого и 0-1. Бихам, Миддлтон и Левин (1992) описывают двумерную модель городской сетки , в которой динамика отдельных полос движения по существу соответствует правилу 184. [16] Для углубленного исследования моделирования трафика клеточными автоматами и связанной с ним статистической механики см. Maerivoet & De Moor (2005) и Chowdhury, Santen & Schadschneider (2000).
Рассматривая Правило 184 как модель дорожного движения, естественно учитывать среднюю скорость транспортных средств. Когда плотность движения менее 50%, эта средняя скорость составляет всего лишь одну единицу расстояния в единицу времени: после того, как система стабилизируется, ни один автомобиль никогда не замедляется. Однако, когда плотность равна числу ρ больше 1/2, средняя скорость движения равна . Таким образом, в системе наблюдается кинетический фазовый переход второго рода при ρ = 1/2 . Когда Правило 184 интерпретируется как модель дорожного движения и начинается со случайной конфигурации, плотность которой находится на этом критическом значении ρ = 1/2 , тогда средняя скорость приближается к своему стационарному пределу как квадратный корень из количества шагов. Вместо этого для случайных конфигураций, плотность которых не достигает критического значения, приближение к предельной скорости является экспоненциальным. [17]
Как показано на рисунке и первоначально описано Krug & Spohn (1988), [18] Правило 184 можно использовать для моделирования осаждения частиц на поверхность. В этой модели имеется набор частиц, которые занимают подмножество позиций в квадратной решетке, ориентированной по диагонали (более темные частицы на рисунке). Если частица присутствует в некоторой позиции решетки, позиции решетки ниже и справа, а также ниже и слева от частицы также должны быть заполнены, поэтому заполненная часть решетки простирается бесконечно вниз влево и вправо. . Граница между заполненными и незаполненными позициями (тонкая черная линия на рисунке) интерпретируется как моделирование поверхности, на которую может быть осаждено больше частиц. На каждом временном шаге поверхность растет за счет осаждения новых частиц в каждом локальном минимуме поверхности; то есть в каждой позиции, где можно добавить одну новую частицу, под которой с обеих сторон есть существующие частицы (более легкие частицы на рисунке).
Чтобы смоделировать этот процесс по Правилу 184, заметим, что граница между заполненными и незаполненными позициями решетки может быть отмечена ломаной линией, сегменты которой разделяют соседние позиции решетки и имеют наклоны +1 и -1. Моделируйте сегмент с наклоном +1 автоматной клеткой с состоянием 0, а сегмент с наклоном -1 - автоматной ячейкой с состоянием 1. Локальными минимумами поверхности являются точки, в которых сегмент с наклоном -1 лежит слева. участка склона +1; то есть в автомате это позиция, в которой ячейка с состоянием 1 лежит слева от ячейки с состоянием 0. Добавление частицы в эту позицию соответствует изменению состояний этих двух соседних ячеек с 1,0 на 0,1. , поэтому продвигаем ломаную линию. Именно так ведет себя Правило 184. [19]
Сопутствующая работа по этой модели касается осаждения, при котором время прибытия дополнительных частиц является случайным, а не когда частицы достигают всех локальных минимумов одновременно. [20] Эти стохастические процессы роста можно смоделировать как асинхронный клеточный автомат .
Баллистическая аннигиляция описывает процесс, при котором движущиеся частицы и античастицы аннигилируют друг друга при столкновении. В простейшем варианте этого процесса система состоит из одного типа частиц и античастиц, движущихся с равными скоростями в противоположных направлениях в одномерной среде. [21]
Этот процесс можно смоделировать с помощью Правила 184 следующим образом. Частицы моделируются как точки, совмещенные не с ячейками автомата, а с промежутками между ячейками. Две последовательные ячейки, обе из которых имеют состояние 0, моделируют частицу в пространстве между этими двумя ячейками, которая перемещается на одну ячейку вправо на каждом временном шаге. Симметрично, две последовательные ячейки, обе из которых имеют состояние 1, моделируют античастицу, которая перемещается на одну ячейку влево на каждом временном шаге. Остальные возможности для двух последовательных ячеек заключаются в том, что они обе имеют разные состояния; это интерпретируется как моделирование фонового материала без каких-либо частиц, через который частицы движутся. При такой интерпретации частицы и античастицы взаимодействуют путем баллистической аннигиляции: когда частица, движущаяся вправо, и античастица, движущаяся влево, встречаются, в результате образуется область фона, из которой обе частицы исчезли, без какого-либо влияния на другие близлежащие частицы. [22]
Поведение некоторых других систем, таких как одномерные циклические клеточные автоматы , также можно описать в терминах баллистической аннигиляции. [23] Существует техническое ограничение на положение частиц для точки зрения баллистического уничтожения Правила 184, которое не возникает в этих других системах, вытекающее из чередующегося рисунка фона: в системе частиц, соответствующей состоянию Правила 184, если две последовательные частицы относятся к одному и тому же типу, они должны находиться на нечетном количестве ячеек друг от друга, а если они принадлежат к противоположным типам, они должны находиться на четном количестве ячеек друг от друга. Однако это ограничение четности не играет роли в статистическом поведении этой системы.
Пивато (2007) использует аналогичный, но более сложный взгляд на Правило 184 с точки зрения системы частиц: он не только рассматривает чередующиеся области 0–1 как фон, но также считает фоном регионы, состоящие исключительно из одного состояния. Основываясь на этой точке зрения, он описывает семь различных частиц, образованных границами между областями, и классифицирует их возможные взаимодействия. См. Chopard & Droz (1998, стр. 188–190) для более общего обзора клеточно-автоматных моделей процессов аннигиляции.
В своей книге A New Kind of Science Стивен Вольфрам указывает , что правило 184 при его выполнении на шаблонах с плотностью 50% можно интерпретировать как анализ контекстно-свободного языка, описывающего строки, образованные из вложенных круглых скобок . Эта интерпретация тесно связана с точкой зрения баллистического уничтожения правила 184: в интерпретации Вольфрама открывающая скобка соответствует частице, движущейся влево, а закрывающая скобка соответствует частице, движущейся вправо. [24]
