Правило 184

Правило 184: пройдите 128 шагов из случайных конфигураций с тремя различными начальными плотностями: верхние 25%, средние 50%, нижние 75%. Показанный вид представляет собой кадрирование размером 300 пикселей из более широкой симуляции.

Правило 184 — это одномерное бинарное правило клеточного автомата , примечательное решением проблемы большинства , а также способностью одновременно описывать несколько, казалось бы, совершенно разных систем частиц :

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

Кажущееся противоречие между этими описаниями разрешается различными способами связи особенностей состояния автомата с частицами.

Название Правила 184 — это код Вольфрама , определяющий эволюцию его состояний. Самое раннее исследование Правила 184 было проведено Ли (1987) и Krug & Spohn (1988) . В частности, Круг и Спон уже описывают все три типа систем частиц, смоделированных Правилом 184.

Определение

Состояние автомата по Правилу 184 состоит из одномерного массива ячеек, каждая из которых содержит двоичное значение (0 или 1). На каждом этапе своей эволюции автомат «Правило 184» применяет следующее правило к каждой ячейке массива одновременно для всех ячеек, чтобы определить новое состояние ячейки:

текущий шаблон	111	110	101	100	011	010	001	000
новое состояние центральной ячейки	1	0	1	1	1	0	0	0

Запись в этой таблице определяет новое состояние каждой ячейки как функцию предыдущего состояния и предыдущих значений соседних ячеек с обеих сторон.Название этого правила, Правило 184, — это код Вольфрама, описывающий приведенную выше таблицу состояний: нижняя строка таблицы, 10111000, если рассматривать ее как двоичное число , равна десятичному числу 184 .

Набор правил для Правила 184 также можно описать интуитивно несколькими способами:

• На каждом этапе, когда в текущем состоянии существует 1, за которой сразу следует 0, эти два символа меняются местами. Основываясь на этом описании, Круг и Спон (1988) называют Правило 184 детерминистической версией «кинетической модели Изинга с асимметричной динамикой спинового обмена».
• На каждом шаге, если справа от ячейки со значением 1 находится ячейка со значением 0, 1 перемещается вправо, оставляя 0 позади. 1 с еще одной 1 справа остается на месте, а 0, у которого нет 1 слева, остается 0. Это описание наиболее подходит для применения в моделировании транспортных потоков.
• Если ячейка имеет состояние 0, ее новое состояние берется из ячейки слева от нее. В противном случае его новое состояние берется из ячейки справа от нее. То есть каждая ячейка может быть реализована с помощью двустороннего демультиплексора, при этом две соседние ячейки являются входами, а сама ячейка действует как линия выбора. Следующее состояние каждой ячейки определяется выходным сигналом демультиплексора. Эта операция тесно связана с вентилем Фредкина .

Динамика и классификация большинства

Из описаний правил, приведенных выше, сразу можно увидеть два важных свойства его динамики. Во-первых, в Правиле 184 для любого конечного набора ячеек с периодическими граничными условиями количество единиц и количество нулей в шаблоне остается неизменным на протяжении всего развития шаблона. Правило 184 и его отражение — единственные нетривиальные элементарные клеточные автоматы обладают этим свойством сохранения числа. Аналогично, если плотность единиц четко определена для бесконечного массива ячеек, она остается неизменной во время выполнения автоматом своих шагов. И во-вторых, хотя правило 184 не является симметричным при перестановке слева направо, оно имеет другую симметрию: перестановка слева и справа и в то же время замена ролей символов 0 и 1 дает клеточный автомат с тем же правилом обновления.

Шаблоны в Правиле 184 обычно быстро стабилизируются либо до шаблона, в котором состояния ячеек синхронно перемещаются на одну позицию влево на каждом шаге, либо до шаблона, который перемещается на одну позицию вправо на каждом шаге. В частности, если начальная плотность ячеек с состоянием 1 составляет менее 50%, паттерн стабилизируется в кластеры ячеек в состоянии 1, расположенные на расстоянии двух единиц друг от друга, причем кластеры разделены блоками ячеек в состоянии 0. Паттерны этого типа перемещаются. вправо. Если, с другой стороны, начальная плотность превышает 50%, паттерн стабилизируется в кластеры ячеек в состоянии 0, расположенные на расстоянии двух единиц друг от друга, причем кластеры разделены блоками ячеек в состоянии 1, и паттерны этого типа перемещаются. влево. Если плотность составляет точно 50%, исходный паттерн стабилизируется (более медленно) до паттерна, который эквивалентно можно рассматривать как движение либо влево, либо вправо на каждом шаге: чередующуюся последовательность 0 и 1.

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

Транспортный поток

Правило 184 интерпретируется как моделирование транспортного потока. Каждая 1 ячейка соответствует транспортному средству, и каждое транспортное средство движется вперед только в том случае, если перед ним есть открытое пространство.

Если интерпретировать каждую 1-клетку в Правиле 184 как содержащую частицу, эти частицы во многом ведут себя аналогично автомобилям, движущимся по одной полосе движения: они движутся вперед с постоянной скоростью, если перед ними есть открытое пространство, и в противном случае они останавливаются. Модели трафика, такие как Правило 184 и его обобщения, которые дискретизируют как пространство, так и время, обычно называются моделями скачкообразного перемещения частиц . Хотя модель транспортного потока по Правилу 184 очень примитивна, она уже предсказывает некоторые знакомые возникающие особенности реального дорожного движения: группы свободно движущихся автомобилей, разделенные участками открытой дороги, когда движение слабое, и волны движения с остановками, когда движение ограничено. тяжелый.

Трудно определить первое использование Правила 184 для моделирования транспортных потоков, отчасти потому, что исследования в этой области были направлены не столько на достижение максимального уровня математической абстракции, сколько на правдоподобие: даже более ранние статьи по клеточным автоматам, основанные на Моделирование транспортных потоков обычно усложняет модель, чтобы более точно имитировать реальный трафик. Тем не менее, Правило 184 имеет основополагающее значение для моделирования трафика клеточными автоматами. Ван, Квонг и Хуэй (1998) , например, утверждают, что «базовой моделью клеточного автомата, описывающей одномерную проблему транспортного потока, является правило 184». Нагель (1996) пишет: «Большая часть работ по использованию моделей CA для трафика основана на этой модели». Некоторые авторы описывают одномерные модели транспортных средств, движущихся с разными скоростями; такие модели вырождаются до правила 184 в случае односкоростного режима. Gaylord & Nishidate (1996) распространяют действие Правила 184 на двухполосное движение по шоссе со сменой полос движения; их модель и Правило 184 имеют то общее свойство, что она симметрична при одновременном развороте левого-правого и 0-1. Бихам, Миддлтон и Левин (1992) описывают двумерную модель городской сетки , в которой динамика отдельных полос движения по существу аналогична Правилу 184. Подробный обзор моделирования трафика клеточных автоматов и связанной с ним статистической механики см. в Maerivoet & De Moor (2005) и Chowdhury, Santen & Schadschneider (2000) .

Рассматривая Правило 184 как модель дорожного движения, естественно учитывать среднюю скорость транспортных средств. Когда плотность движения менее 50%, эта средняя скорость составляет всего лишь одну единицу расстояния в единицу времени: после того, как система стабилизируется, ни один автомобиль никогда не замедляется. Однако, когда плотность равна числу ρ больше 1/2, средняя скорость движения равна ${\tfrac {1-\rho }{\rho }}$. второго рода Таким образом, в системе наблюдается кинетический фазовый переход при ρ = 1/2 . Когда правило 184 интерпретируется как модель дорожного движения и начинается со случайной конфигурации, плотность которой находится на этом критическом значении ρ = 1/2 , тогда средняя скорость приближается к своему стационарному пределу как квадратный корень из количества шагов. Вместо этого для случайных конфигураций, плотность которых не достигает критического значения, приближение к предельной скорости является экспоненциальным.

Поверхностное осаждение

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

Как показано на рисунке и первоначально описано Krug & Spohn (1988) , Правило 184 можно использовать для моделирования осаждения частиц на поверхность. В этой модели имеется набор частиц, которые занимают подмножество позиций в квадратной решетке, ориентированной по диагонали (более темные частицы на рисунке). Если частица присутствует в каком-то положении решетки, позиции решетки ниже и справа, а также ниже и слева от частицы также должны быть заполнены, поэтому заполненная часть решетки простирается бесконечно вниз влево и вправо. . Граница между заполненными и незаполненными позициями (тонкая черная линия на рисунке) интерпретируется как моделирование поверхности, на которую может быть осаждено больше частиц. На каждом временном шаге поверхность растет за счет осаждения новых частиц в каждом локальном минимуме поверхности; то есть в каждой позиции, где можно добавить одну новую частицу, под которой с обеих сторон есть существующие частицы (более легкие частицы на рисунке).

Чтобы смоделировать этот процесс по Правилу 184, заметим, что граница между заполненными и незаполненными позициями решетки может быть отмечена ломаной линией, сегменты которой разделяют соседние позиции решетки и имеют наклоны +1 и -1. Смоделируйте сегмент с наклоном +1 автоматной клеткой с состоянием 0, а сегмент с наклоном -1 - автоматной ячейкой с состоянием 1. Локальными минимумами поверхности являются точки, в которых сегмент с наклоном -1 лежит слева. участка склона +1; то есть в автомате это позиция, в которой ячейка с состоянием 1 лежит слева от ячейки с состоянием 0. Добавление частицы в эту позицию соответствует изменению состояний этих двух соседних ячеек с 1,0 на 0,1. , поэтому продвигаем ломаную линию. Именно так ведет себя Правило 184.

Сопутствующая работа по этой модели касается осаждения, при котором время прибытия дополнительных частиц является случайным, а не когда частицы достигают всех локальных минимумов одновременно. Эти стохастические процессы роста можно смоделировать как асинхронный клеточный автомат .

Баллистическое уничтожение

Правило 184 как модель баллистического уничтожения. Частицы и античастицы (моделированные последовательными ячейками с одинаковым состоянием) движутся в противоположных направлениях и аннигилируют друг друга при столкновении.

Баллистическая аннигиляция описывает процесс, при котором движущиеся частицы и античастицы аннигилируют друг друга при столкновении. В простейшем варианте этого процесса система состоит из одного типа частиц и античастиц, движущихся с равными скоростями в противоположных направлениях в одномерной среде.

Этот процесс можно смоделировать с помощью Правила 184 следующим образом. Частицы моделируются как точки, совмещенные не с ячейками автомата, а с промежутками между ячейками. Две последовательные ячейки, обе из которых имеют состояние 0, моделируют частицу в пространстве между этими двумя ячейками, которая перемещается на одну ячейку вправо на каждом временном шаге. Симметрично, две последовательные ячейки, обе из которых имеют состояние 1, моделируют античастицу, которая перемещается на одну ячейку влево на каждом временном шаге. Остальные возможности для двух последовательных ячеек заключаются в том, что они обе имеют разные состояния; это интерпретируется как моделирование фонового материала без каких-либо частиц, через который частицы движутся. При такой интерпретации частицы и античастицы взаимодействуют путем баллистической аннигиляции: когда частица, движущаяся вправо, и античастица, движущаяся влево, встречаются, в результате образуется область фона, из которой обе частицы исчезли, без какого-либо влияния на другие близлежащие частицы.

Поведение некоторых других систем, таких как одномерные циклические клеточные автоматы , также можно описать в терминах баллистической аннигиляции. Существует техническое ограничение на положение частиц для точки зрения баллистической аннигиляции Правила 184, которое не возникает в этих других системах, вытекающее из чередующегося рисунка фона: в системе частиц, соответствующей состоянию Правила 184, если две последовательные частицы оба относятся к одному и тому же типу, между ними должно быть нечетное количество ячеек, а если они относятся к противоположным типам, между ними должно быть четное количество ячеек. Однако это ограничение четности не играет роли в статистическом поведении этой системы.

Пивато (2007) использует аналогичный, но более сложный взгляд на Правило 184 с точки зрения системы частиц: он не только рассматривает чередующиеся области 0–1 как фон, но также считает фоном регионы, состоящие исключительно из одного состояния. Основываясь на этой точке зрения, он описывает семь различных частиц, образованных границами между областями, и классифицирует их возможные взаимодействия. См. Chopard & Droz (1998 , стр. 188–190) для более общего обзора клеточно-автоматных моделей процессов аннигиляции.

Контекстно-свободный анализ

В своей книге A New Kind of Science Стивен Вольфрам указывает, что правило 184 при его выполнении на шаблонах с плотностью 50% можно интерпретировать как анализ контекстно-свободного языка, описывающего строки, образованные из вложенных круглых скобок . Эта интерпретация тесно связана с представлением правила 184 о баллистическом уничтожении: в интерпретации Вольфрама открывающая скобка соответствует частице, движущейся влево, а закрывающая скобка соответствует частице, движущейся вправо.

См. также

• Правило 30 , Правило 90 и Правило 110 , другие одномерные клеточные автоматы с другим поведением.

Ссылки

• Алонсо-Санс, Рамон (2011). «Правила сохранения чисел» . Дискретные системы с памятью . Всемирная научная серия по нелинейной науке, Сер. А. Том. 75. Всемирный научный. стр. 55–57. ISBN  9789814343633 .
• Белицкий Владимир; Феррари, Пабло А. (1995). «Баллистическая аннигиляция и детерминированный рост поверхности». Журнал статистической физики . 80 (3–4): 517–543. Бибкод : 1995JSP....80..517B . CiteSeerX   10.1.1.4.7901 . дои : 10.1007/BF02178546 . S2CID   16293185 .
• Бихам, Офер ; Миддлтон, А. Алан; Левин, Дов (1992). «Самоорганизация и динамический переход в моделях транспортных потоков». Физический обзор А. 46 (10): Р6124–Р6127. arXiv : cond-mat/9206001 . Бибкод : 1992PhRvA..46.6124B . дои : 10.1103/PhysRevA.46.R6124 . ПМИД   9907993 . S2CID   14543020 .
• Боккара, Нино; Фукс, Хенрик (1998). «Правила клеточного автомата, сохраняющие количество активных сайтов». Журнал физики A: Математический и общий . 31 (28): 6007–6018. arXiv : adap-org/9712003 . Бибкод : 1998JPhA...31.6007B . дои : 10.1088/0305-4470/31/28/014 . S2CID   14807539 .
• Капкаррер, Матье С.; Сиппер, Моше; Томассини, Марко (1996). «Клеточный автомат с двумя состояниями, r = 1, классифицирующий плотность» (PDF) . Письма о физических отзывах . 77 (24): 4969–4971. Бибкод : 1996PhRvL..77.4969C . doi : 10.1103/PhysRevLett.77.4969 . ПМИД   10062680 .
• Шопар, Бастьен; Дро, Мишель (1998). Клеточные автоматы Моделирование физических систем . Издательство Кембриджского университета . ISBN  978-0-521-67345-7 .
• Чоудхури, Дебашиш; Сантен, Людгер; Шадшнайдер, Андреас (2000). «Статистическая физика автомобильного движения и некоторые связанные с ней системы». Отчеты по физике . 329 (4): 199–329. arXiv : cond-mat/0007053 . Бибкод : 2000PhR...329..199C . дои : 10.1016/S0370-1573(99)00117-9 . S2CID   119526662 .
• Фукс, Хенрик (1997). «Решение задачи плотности классификации с двумя одинаковыми правилами клеточных автоматов». Физический обзор E . 55 (3): R2081–R2084. arXiv : комп-газ/9703001 . Бибкод : 1997PhRvE..55.2081F . дои : 10.1103/PhysRevE.55.R2081 . S2CID   118954791 .
• Фукс, Хенрик; Боккара, Нино (1998). «Обобщенные детерминированные правила дорожного движения» (PDF) . Международный журнал современной физики C . 9 (1): 1–12. arXiv : adap-org/9705003 . Бибкод : 1998IJMPC...9....1F . дои : 10.1142/S0129183198000029 . S2CID   119938282 . Архивировано из оригинала (PDF) 27 сентября 2007 года.
• Фукуи, М.; Ишибаши, Ю. (1996). «Транспортный поток в одномерной модели клеточного автомата, включая автомобили, движущиеся с высокой скоростью». Журнал Физического общества Японии . 65 (6): 1868–1870. Бибкод : 1996JPSJ...65.1868F . дои : 10.1143/JPSJ.65.1868 .
• Гейлорд, Ричард Дж.; Нисидатэ, Кадзуме (1996). «Транспортный поток». Моделирование природы: моделирование клеточных автоматов с помощью Mathematica . Спрингер-Верлаг . стр. 29–34 . ISBN  978-0-387-94620-7 .
• Круг, Дж.; Спон, Х. (1988). «Классы универсальности для детерминированного роста поверхности». Физический обзор А. 38 (8): 4271–4283. Бибкод : 1988PhRvA..38.4271K . дои : 10.1103/PhysRevA.38.4271 . ПМИД   9900880 .
• Земля, Марк; Белью, Ричард (1995). «Не существует идеальных клеточных автоматов с двумя состояниями для классификации по плотности». Письма о физических отзывах . 74 (25): 1548–1550. Бибкод : 1995PhRvL..74.5148L . doi : 10.1103/PhysRevLett.74.5148 . ПМИД   10058695 .
• Ли, Вэньтянь (1987). «Спектры мощности регулярных языков и клеточных автоматов» (PDF) . Сложные системы . 1 : 107–130. Архивировано из оригинала (PDF) 7 октября 2007 г.
• Ли, Вэньтянь (1992). «Феноменология нелокальных клеточных автоматов». Журнал статистической физики . 68 (5–6): 829–882. Бибкод : 1992JSP....68..829L . CiteSeerX   10.1.1.590.1708 . дои : 10.1007/BF01048877 . S2CID   17337112 .
• Маеривет, Свен; Де Мур, Барт (2005). «Клеточно-автоматные модели дорожного движения». Отчеты по физике . 419 (1): 1–64. arXiv : физика/0509082 . Бибкод : 2005ФР...419....1М . doi : 10.1016/j.physrep.2005.08.005 . S2CID   41394950 .
• Морейра, Андрес (2003). «Универсальность и разрешимость сохраняющих число клеточных автоматов». Теоретическая информатика . 292 (3): 711–721. arXiv : nlin.CG/0306032 . Бибкод : 2003nlin......6032M . дои : 10.1016/S0304-3975(02)00065-8 . S2CID   14909462 .
• Нагель, Кай (1996). «Модели скачкообразных частиц и теория транспортных потоков». Физический обзор E . 53 (5): 4655–4672. arXiv : cond-mat/9509075 . Бибкод : 1996PhRvE..53.4655N . дои : 10.1103/PhysRevE.53.4655 . ПМИД   9964794 . S2CID   20466753 .
• Нагель, Кай; Шрекенберг, Майкл (1992). «Модель клеточного автомата для движения по автостраде» . Журнал де Физика I. 2 (12): 2221–2229. Бибкод : 1992JPhy1...2.2221N . дои : 10.1051/jp1:1992277 . S2CID   37135830 .
• Пивато, М. (2007). «Кинематика дефектных частиц в одномерных клеточных автоматах». Теоретическая информатика . 377 (1–3): 205–228. arXiv : math.DS/0506417 . дои : 10.1016/j.tcs.2007.03.014 . S2CID   12650387 .
• Реднер, Сидни (2001). «8.5 Баллистическое уничтожение» . Руководство по процессам первого прохождения . Издательство Кембриджского университета . п. 288. ИСБН  9780521652483 .
• Сукумар, Н. (1998). «Влияние граничных условий на клеточные автоматы, классифицирующие плотность». arXiv : комп-газ/9804001 .
• Тадаки, Синъити; Кикучи, Макато (1994). «Фазы пробок в двумерной клеточно-автоматной модели транспортного потока». Физический обзор E . 50 (6): 4564–4570. arXiv : patt-sol/9409004 . Бибкод : 1994PhRvE..50.4564T . дои : 10.1103/PhysRevE.50.4564 . ПМИД   9962535 . S2CID   17516156 .
• Ван, Бин-Хонг; Квонг, Ивонн-Роами; Хуэй, Пак-Мин (1998). «Статистически-механический подход к моделям транспортных потоков Фукуи-Исибаши». Физический обзор E . 57 (3): 2568–2573. Бибкод : 1998PhRvE..57.2568W . дои : 10.1103/PhysRevE.57.2568 .
• Вольфрам, Стивен (2002). Новый вид науки . Вольфрам Медиа .

Внешние ссылки

• Правило 184 в атласе клеточных автоматов Вольфрама.