Правило Тома

Правило Тума — это двумерная модель клеточного автомата , созданная Андреем Тоомом в 1978 году. ^{[ 1 ]}^{[ 2 ]} Это модификация двумерного правила большинства голосов, которая может иметь более надежную память, если рассматривать ее как теплофизическую систему в статистической теории поля . ^{[ 3 ]} Модель также имеет шумозависимый фазовый переход . ^{[ 1 ]}

Заявление

Правило Тума представляет собой клеточный автомат, действующий на двумерной квадратной решетке. В каждом узле этой решетки находится спин со значением +1 или -1. Во время $t=0$ биты инициализируются некоторым значением. На каждом дискретном шаге времени $(t>0)$ решетка развивается по правилу Тоума. Это правило применяется на каждом объекте одновременно.

Детерминированную версию правила Тума можно сформулировать так:

Если в каждом узле решетки спин текущего (центрального) узла плюс соседний спин на север плюс соседний спин на восток больше 0, то текущий спин становится +1 на следующем временном шаге.
Если эта сумма меньше 0, то текущий спин станет -1 на следующем временном шаге. Поскольку вращений 3, сумма никогда не может равняться 0.

Правило Тума иногда называют правилом NEC, поскольку оно касается северных, восточных и центральных участков. ^{[ 1 ]}

Общая версия правила Тоума является вероятностной и может быть сформулирована как:

Примените детерминированную версию правила Тума.
Если шаг 1 приводит к спину +1, измените его на -1 с вероятностью q. В противном случае, если на шаге 2 спин равен -1, измените его на +1 с вероятностью p. ^{[ 4 ]}

Детерминированную версию можно восстановить, установив p=q=0.

Правило Тума — пример вероятностного клеточного автомата (см. Стохастический клеточный автомат ), определенного на решетке $\mathbb {Z} ^{2}$ . ^{[ 1 ]}

Характеристики

Когда $p\neq q$ система будет иметь тенденцию отдавать предпочтение одному спину перед другим, что можно интерпретировать как эффект магнитного поля . ^{[ 1 ]}

Модель имеет фазовый переход . При достаточно низких p, q существует по крайней мере два устойчивых состояния, но при достаточно высоких p, q существует единственное устойчивое состояние. ^{[ 1 ]} Это доказано в оригинальной статье Тума. ^{[ 2 ]}

Когда p=q=0, существует устойчивое состояние с лестничной границей (интерфейсом) между спинами +1 и -1. Когда p, q малы, вдоль этой границы возникают флуктуации. Дополнительные модели были построены для изучения динамики интерфейса как одномерной спиновой конфигурации (на $\mathbb {Z} _{+}$ ).

Можно определить $\lambda _{+}$ как вероятность (вероятность) того, что каждый +1 поменяется местами с первым спином -1 справа от него. Ставка $\lambda _{-}$ можно определить аналогично. Можно сделать дальнейшее упрощение: только самый левый спин в блоке (из идентичных спинов) меняется местами с первым противоположным спином справа. Кроме того, пусть первый спин переворачивается независимо с вероятностью $\alpha$ . Эту одномерную модель также называют правилом Тоума. ^{[ 1 ]}

При изучении установившегося состояния, когда $\lambda _{+}=\lambda _{-}=\alpha$ , плотность узла n (ожидаемое значение узла n) подчиняется масштабному закону: ^{[ 1 ]}

$\langle \sigma _{n}\rangle \sim {\frac {1}{2{\sqrt {\pi n}}}}$

Можно также определить конечную версию этого 1D-правила Тума, где имеется L сайтов (модель конечного интерфейса). Крайняя левая -1 в блоке с вероятностью обменивается с первой +1 справа. $\alpha$ , а крайний +1 в блоке с вероятностью меняется на первый -1 справа $\beta$ . В этой модели имеется u спинов вверх и d спинов вниз, где u+d=L. Есть также ${\binom {L}{u}}$ конфигурации L сайтов. ^{[ 1 ]}

Корреляционные функции , статистическая сумма , матрицы Маркова и их собственные значения могут быть вычислены для этого конечного правила Тума. Было показано, что когда $\alpha =\beta$ и больших n < L, функция плотности подчиняется тому же закону обратных квадратов, что и выше: $\langle \sigma _{n}\rangle \sim {\frac {1}{2{\sqrt {\pi n}}}}$ .

Когда $\alpha \neq \beta$ предполагается, что плотность убывает как 1/n. ^{[ 1 ]}

Правило Тоума как память

Правило Тума — динамический вариант модели Изинга . Существует множество динамических правил для модели Изинга, где устойчивое состояние является гиббсовским . ^{[ 1 ]}

Двумерная ферромагнитная модель Изинга в отсутствие локальных магнитных полей имеет два основных состояния: одно, когда все спины в решетке имеют +1 (спин вверх), и другое, когда все спины в решетке имеют -1 (спин вниз). По этой причине двумерную модель Изинга можно рассматривать как память, хранящую один бит информации в основном состоянии.

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

Двумерный клеточный автомат большинства голосов (КА) аналогичен модели Изинга. CA большинства голосов развивает каждый узел в решетке, принимая значение вращения текущего узла плюс значение спина четырех соседних узлов и делает этот спин +1 на следующем временном шаге, если сумма положительна, и -1, если сумма отрицательна. Как и в случае с правилом Тума, мы можем построить вероятностную версию СА большинства голосов, в которой выходной сигнал может быть изменен с вероятностью q со спина +1 на спин -1 и с вероятностью p со спина -1 на спин +1.

Вместо основных состояний информация хранится в стабильных состояниях СА. Это состояния, в которых спины решетки не изменяются под действием КА. Легко показать, что состояния «все +1» и «все -1» являются стабильными состояниями, когда q=p=0. Следовательно, CA большинства голосов можно использовать для хранения информации. Мы можем определить термины, аналогичные тепловому шуму и магнитному полю, как T=p+q и h=(pq)/(p+q) соответственно. Подобно модели Изинга, CA большинства голосов может надежно хранить информацию для малых значений T. В отличие от режима Изинга, если T достаточно мало, это справедливо даже для произвольных значений h. ^{[ 4 ]}^{[ 5 ]}

Модель Тума может быть применена к отказоустойчивым вычислениям. ^{[ 5 ]}

Ссылки

^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к Айер, Арвинд (август 2015 г.). «Конечный вариант модели Тума» . Физический журнал: серия конференций . 638 (1): 012005. arXiv : 1503.00086 . дои : 10.1088/1742-6596/638/1/012005 . ISSN 1742-6596 .
^ Перейти обратно: ^а ^б Тоом, Андрей (1980). «Стабильные и привлекательные траектории в многокомпонентных системах». Многокомпонентные случайные системы : 549–575.
^ Бернд Гартнер, Ахад Н. Земакан (2017). «Цветная война: клеточные автоматы с правилом большинства». Лата 2017 : 393–404.
^ Перейти обратно: ^а ^б Гринштейн, Г. (1 января 2004 г.). «Могут ли сложные структуры быть в целом стабильными в шумном мире?». Журнал исследований и разработок IBM . 48 (1): 5–12. дои : 10.1147/rd.481.0005 .
^ Перейти обратно: ^а ^б Гакс, Питер. « Новая версия доказательства Тума», Технический отчет BUCS-1995-009, Факультет компьютерных наук, Бостонский университет, 27 марта 1995 г.» . Бостонский университет . Проверено 8 апреля 2020 г.

[:0-1] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к Айер, Арвинд (август 2015 г.). «Конечный вариант модели Тума» . Физический журнал: серия конференций . 638 (1): 012005. arXiv : 1503.00086 . дои : 10.1088/1742-6596/638/1/012005 . ISSN 1742-6596 .

[:2-2] Перейти обратно: ^а ^б Тоом, Андрей (1980). «Стабильные и привлекательные траектории в многокомпонентных системах». Многокомпонентные случайные системы : 549–575.

[3] Бернд Гартнер, Ахад Н. Земакан (2017). «Цветная война: клеточные автоматы с правилом большинства». Лата 2017 : 393–404.

[Grinstein-4] Перейти обратно: ^а ^б Гринштейн, Г. (1 января 2004 г.). «Могут ли сложные структуры быть в целом стабильными в шумном мире?». Журнал исследований и разработок IBM . 48 (1): 5–12. дои : 10.1147/rd.481.0005 .

[:1-5] Перейти обратно: ^а ^б Гакс, Питер. « Новая версия доказательства Тума», Технический отчет BUCS-1995-009, Факультет компьютерных наук, Бостонский университет, 27 марта 1995 г.» . Бостонский университет . Проверено 8 апреля 2020 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]