Клеточный автомат Гринберга – Гастингса
 | Эта статья написана как личное размышление, личное эссе или аргументативное эссе , в котором излагаются личные чувства редактора Википедии или представлен оригинальный аргумент по определенной теме. ( Ноябрь 2013 г. ) |
Клеточный автомат Гринберга-Гастингса (сокр. Модель GH ) — это двумерный клеточный автомат с тремя состояниями (сокр. CA ), названный в честь Джеймса М. Гринберга и Стюарта Гастингса, [1] предназначен для моделирования возбудимых сред , [2] Одним из преимуществ модели CA является простота вычислений. Модель достаточно хорошо можно понять, используя простые «ручные» расчеты, не привлекая компьютер. [2] Другое преимущество состоит в том, что, по крайней мере в этом случае, можно доказать теорему, характеризующую те начальные условия, которые приводят к повторяющемуся поведению. [3]
Неофициальное описание
[ редактировать ]Как и в типичном двумерном клеточном автомате , [1] рассмотрим прямоугольную сетку или шахматную доску из «ячеек». Оно может быть конечным или бесконечным по размеру. Каждая ячейка имеет набор «соседей». В простейшем случае каждая ячейка имеет четырех соседей, причем это ячейки непосредственно выше или ниже, либо слева или справа от данной ячейки. [2]
Вот так: все b являются соседями a. a является одним из соседей каждого из b.
b
b a b
b
В каждый «время» t=0,1,2,3,.... каждой клетке присваивается одно из трех «состояний», обычно называемых «покоем» (или «покоем»; см. возбудимую среду ), «возбуждением». , или «огнеупорный». [2] Назначение состояний для всех ячеек произвольно в течение t = 0, а затем в последующие моменты времени состояние каждой ячейки определяется по следующим правилам. [2]
1. Если в момент времени t клетка находится в возбужденном состоянии, то в момент времени t+1 она находится в рефрактерном состоянии.
2. Если в момент времени t клетка находится в рефрактерном состоянии, то в момент времени t+1 она находится в состоянии покоя.
3. Если данная клетка находится в состоянии покоя в момент времени t и хотя бы один из ее соседей находится в возбужденном состоянии в момент времени t, то данная клетка находится в возбужденном состоянии в момент времени t+1, в противном случае (ни один сосед не находится в состоянии покоя в момент времени t+1). возбужденный в момент t), он остается в состоянии покоя в момент t+1.
Таким образом, вся сетка ячеек перемещается от их начальных состояний при t = 0 к их состояниям при t = 1, затем к их состояниям при t = 2,3,4 и т. д., создавая структуру ячеек в различных состояниях. за каждый раз.
Посмотрите первую анимацию реакции Белоусова-Жаботинского, чтобы увидеть яркий пример поведения, которое может демонстрировать эта модель. Три состояния обозначены разными цветами.
Математическое описание
[ редактировать ]Чтобы описать модель GH более математически, рассмотрим простейший случай сетки квадратных ячеек. . В каждый момент времени клетка имеет государство Тип соседства не имеет значения, если у каждой ячейки есть несколько соседей. В квадратной сетке (в отличие от шестиугольной) нормально работают либо четыре, либо восемь ячеек. Правило эволюции следующее: Если затем . Если затем Если и для какой-то соседней ячейки затем . В противном случае, [1] [2]
Связь с моделью Винера и Розенблюта
[ редактировать ]Модель GH часто сравнивают с новаторской моделью Винера и Розенблюта. [4] разработанная ранее с той же целью, аналогия некорректна, поскольку последний не является СА. См., например, [5] в котором говорится, что «Организация мышечных клеток, сокращение мышц, зависимость активности среды от активности ее составных элементов, проблемы памяти, надежности и подвижности были сформулированы Винером в виде определения и теоремы для трехфазной порого-инвариантной сплошной возбудимой среды». Однако даже это утверждение вводит в заблуждение. Прочитав оригинальную статью [4] внимательно можно увидеть, что ни время, ни среда, ни состояние не являются дискретными. Это сразу же очевидно в отношении времени и среды. Однако Винер и Розенблют говорят: «Есть три условия, при которых может существовать любой данный участок волокна». Они называют их «активным», «рефрактерным» и «остальным» состояниями. Однако в следующем параграфе они уточняют это, обозначая состояние покоя номером 1, активное состояние номером 0 и рефрактерное состояние открытым интервалом (0,1) на реальной линии. Номер, присвоенный точке передачи в данный момент времени, называется ее «номером эпохи» в этот момент. Таким образом, «пространство состояний» — это интервал [0,1]. А в следующем параграфе мы находим «...за каждым свободно движущимся волновым фронтом будет полоса фиксированной ширины, внутри которой происходит процесс восстановления». Таким образом, волна состоит из «фронта», гладкой кривой точек с номером эпохи 0, которая движется в плоскости с постоянной скоростью, за которой следует тугоплавкая область точек с номером эпохи в (0,1) постоянной ширины (в зависимости от от скорости), оставляя после себя область покоя из точек с эпохой номер 1. Это далеко не клеточный автомат и правильнее называть «геометрической» моделью.
Далее в [5] заявлено, что
«Автоматные модели возбудимых сред исследовались в [9] и [10]. Эти модели являются дискретным аналогом среды Винера ». (Модели в их цитатах «[9]» и «[10]» отличаются от GH. )
Многие авторы называют модель Вайнера-Розенблюта клеточным автоматом. Самая ранняя статья, найденная Google Scholar, с четко указанным обозначением. [6] Однако, как упоминалось выше, непрерывность среды Винера-Розенблюта до сих пор не позволила сформулировать столь точную теорему о постоянстве закономерностей, как теорема для GH, которая описана ниже. С другой стороны, несколько теорем сформулированы в [4] которые аналогичны доказанным в , [3] хотя доказательства, приведенные для теорем в [4] менее ясны, чем в [3] из-за особенностей соответствующих моделей.
См. также [7] за часто цитируемое компьютерное исследование, основанное на модели, аналогичной модели Винера и Розенблюта.
Создание спирали
[ редактировать ]Одно интересное поведение наблюдается для окрестности четырех ячеек и квадратной сетки, когда начальное состояние состоит из полулинии возбужденных ячеек (1), уходящей в бесконечность, а ниже этой полулинии - полулинии рефрактерных ячеек (2). Остальные клетки отдыхают, когда t=0. [2]
Так:
................................................................... ....00000000000000000000000000000000000000000000000000000000000.... ....00000000000000000000000000000000000000000000000000000000000.... ....00000000000000000001111111111111111111111111111111111111111.... ....00000000000000000002222222222222222222222222222222222222222.... ....00000000000000000000000000000000000000000000000000000000000.... ....00000000000000000000000000000000000000000000000000000000000.... ...................................................................
Полученную спираль можно увидеть на фото. [2] Эту спираль можно легко увидеть, проследив шаблон вперед на несколько итераций «вручную». Никакой компьютер не нужен.
Теорема
[ редактировать ]Как сказано в, [2] и доказал в [3] (в котором также рассматривались модели с n состояниями), если набор начальных единиц конечен, то каждая отдельная ячейка вечно колеблется в цикле 0,1,2,0 тогда и только тогда, когда в начале есть хотя бы один квадрат из четырех соседние ячейки с одним из следующих шаблонов:
1 2 2 0 0 1
0 0 1 1 2 2
или какое-то отражение или вращение одного из них. Эти закономерности не могут быть уничтожены окружающей средой. Наиболее интересна часть этого результата «только если». Если ни один из этих шаблонов не присутствует в момент t = 0, то в любой ограниченной области шаблон в конечном итоге сводится ко всем нулям. [2] Ключевой инструмент доказательства в [3] - это «число обмотки», которое, как показано, инвариантно для этой модели.
Одним из простых следствий изложенной выше теоремы является то, что если изначально нет «тугоплавких» ячеек, то узор исчезнет в любой ограниченной области (независимо от того, является ли общая сетка конечной или бесконечной по размеру). Это свойство возбудимой среды было обнаружено ранее в работе Винера и Розенблюта. [4] и не выполняется, если в регионе есть «дыры».
Примечания
[ редактировать ]- ^ Перейти обратно: а б с Г. де Врис ; Т. Хиллен; М. Льюис; Дж. Миллер; Б. Шонфиш (2006). «6». Курс математической биологии: количественное моделирование с использованием математических и вычислительных методов . СИАМ.
- ^ Перейти обратно: а б с д и ж г час я дж Дж. М. Гринберг; С. П. Гастингс (1978). «Пространственные закономерности дискретных моделей диффузии в возбудимых средах». SIAM Journal по прикладной математике . 54 (3): 515–523. дои : 10.1137/0134040 .
- ^ Перейти обратно: а б с д и К. Грин, Джеймс; Дж. М. Гринберг, Кертис; С. П. Гастингс, Стюарт (1980). «Комбинаторная задача, возникающая при исследовании уравнений реакции-диффузии». СИАМ Дж. Алгебр. Дискретные методы . 1 (1): 34–42. дои : 10.1137/0601006 .
- ^ Перейти обратно: а б с д и Н. Винер; А. Розенблют (1946). «Математическая формулировка проблемы проводимости связанных возбудимых элементов, в частности в сердечной мышце». Арх. Инст. Кардиол. Мексика . 16 (3): 205–265. ПМИД 20245817 .
- ^ Перейти обратно: а б Летичевский А.А.; Решодко, Л. В. (1974). «Теория Н. Винера о деятельности возбудимых сред». Кибернетика . 8 : 856–864. дои : 10.1007/bf01068458 .
- ^ М. Герхардт; Х. Шустер; Дж. Тайсон (1990). «Клеточно-автоматная модель возбудимых сред: II. Кривизна, дисперсия, вращающиеся волны и извилистые волны». Физика Д. 46 : 392–415. дои : 10.1016/0167-2789(90)90101-T .
- ^ ГК Мо; В. К. Рейнбольдт; Я. А. Абильдсков (1964). «Компьютерная модель мерцательной аритмии». Являюсь. Сердце Дж . 67 : 200–220. дои : 10.1016/0002-8703(64)90371-0 .
Ссылки
[ редактировать ]- Р. Фиш, Дж. Гравнер, Д. Гриффит, Метастабильность в модели Гринберга – Гастингса, Анналы прикладной вероятности , том. 3 (1993), 935–967.
- Р. Дарретт и Дж. Стейф, Некоторые строгие результаты для модели Гринберга – Гастингса, Journal of Theoretical Probability, том 4 (1991), 669–690.
- С. Вольфрам , Новый вид науки , 2003, стр. 1013.