Правило Тоомса - Википедия - Tooms rule

Правило Тоома является двумерным клеточный автомат модель создана Андрей Тоом в 1978 г. (см. [1] для английского перевода). Эта модель является более надежной и простой, чем двумерное правило большинства голосов (см. [2] Больше подробностей).

Окрестности клеточного автомата Тоома.
Анимация правила Тоома. Черные линии - это доменные границы между вращениями вверх и вниз.

Правило Тоома - клеточный автомат, который действует на двумерной квадратной решетке. На каждом узле этой решетки есть спин со значением +1 или -1. Вовремя биты инициализируются некоторым значением. На каждом дискретном временном шаге решетка развивается по правилу Тоома. Это правило применяется одновременно на каждом сайте.

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

Правило Тоома, однако, является вероятностным правилом и может быть сформулировано следующим образом:
(1) Примените детерминированную версию правила Тоома.

Если (1) приводит к вращению +1, измените его на -1 с вероятностью q.
или же
Если (1) приводит к спину -1, измените его на +1 с вероятностью p.[3]

Правило Тоома - случай вероятностных клеточных автоматов (см. Статью Стохастический клеточный автомат ).

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

Плотность + для инвариантного закона модели Тоома. В режиме малых p и q действуют два инвариантных закона.
Окрестности 2D клеточного автомата Изинга.

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

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

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

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

Рекомендации

  1. ^ Тоом, Андрей (1980). «Устойчивые и привлекательные траектории в многокомпонентных системах». Многокомпонентные случайные системы: 549–575.
  2. ^ Бернд Гартнер, Ахад Н. Зехмакан (2017). «Цветная война: клеточные автоматы с правилом большинства». Lata2017: 393–404.
  3. ^ а б Гринштейн, Г. (1 января 2004 г.). «Могут ли сложные конструкции быть стабильными в шумном мире?». Журнал исследований и разработок IBM. 48 (1): 5–12. Дои:10.1147 / rd.481.0005.
  4. ^ Гакс, Питер. ""Новая версия доказательства Тоома ", Технический отчет BUCS-1995-009, Департамент компьютерных наук, Бостонский университет, 27 марта 1995 г.". Бостонский университет. Получено 8 апреля 2020.