Показать меню

Правило 90

26.12.2022
0

Правило 90 (англ. Rule 90) — это элементарный клеточный автомат, то есть одномерный клеточный автомат с двумя состояниями, основанный на функции сложения по модулю 2 (исключающего «ИЛИ», англ. XOR). Наименование «Правило 90» определяется кодом Вольфрама.

Автомат состоит из одномерного массива ячеек, каждая из которых содержит значение 0 («пуста», «мертва») или 1 («заполнена», «жива»). Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей. Правило 90 является простейшим нетривиальным клеточным автоматом. Он детально описан в книге Стивена Вольфрама A New Kind of Science (с англ. — «Наука нового типа»).

Для простейшей конфигурации — начальное положение которой содержит только одну живую ячейку — диаграмма времени-пространства имеет форму треугольника Серпинского. Поведение любой другой конфигурации может быть объяснено путём сложения по модулю 2 простейших конфигураций. В частности, любая конфигурация с конечным числом ненулевых ячеек является репликатором, который постепенно заполняет всё поле своими копиями. Если изначальная конфигурация Правила 90 случайна, то последующие — тоже. Соответствующая диграмма времени-пространства имеет много треугольных «окон» разных размеров, получающихся при постепенном заполнении ряда из нескольких нулей.

Ранние исследования Правила 90 были мотивированы гипотезой Гильбрайта — неразрешённой проблемой из теории чисел, связанной с разностями соседних простых чисел. Также с точки зрения теории чисел интересна последовательность Гулда, содержащая количество ненулевых ячеек на разных шагах в простейшей конфигурации. Её значения — это степени двойки с показателями, равными числу ненулевых цифр в двоичном представлении номеров шага (начиная нумерацию с 0).

У любой конфигурации Правила 90 есть в точности четыре предшественника, поэтому, в отличие от многих других клеточных автоматов вроде Игры «Жизнь», у этого автомата нет сада Эдема, конфигурации без предшественников. Таким образом, Правило 90 является клеточным автоматом, который сюръективен (у каждой конфигурации есть предшественник), но не инъективен (есть конфигурации, которые приводят к одной и той же на следующем шаге), и тем самым даёт контрпример к теореме, обратной к теореме сада Эдема.

Еще по этой теме:
Соглашения по конфигурации
05:00, 17 декабрь
Соглашения по конфигурации
Cоглашения по конфигурации (англ. Convention over configuration, также известен как англ. coding by convention) — концепт (или принцип) проектирования программного обеспечения, заключающийся в том,
Порядок числа по модулю
20:08, 18 декабрь
Порядок числа по модулю
Показателем, или мультипликативным порядком, целого числа a {displaystyle a} по модулю m {displaystyle m}
FN CAL
14:44, 17 декабрь
FN CAL
FN CAL (Carabine Automatique Legere, с фр. — «лёгкий автоматический карабин») — бельгийский автомат. Предназначался для участия в конкурсе на перевооружение Армии США на замену винтовке
Dragon’s Lair
09:57, 15 декабрь
Dragon’s Lair
Dragon’s Lair (с англ. — «Логово дракона») — компьютерная игра, изначально выпущенная в виде игрового автомата компанией Cinematronics в 1983 году. Автомат использовал LaserDisc для
Конечное кольцо
21:26, 07 декабрь
Конечное кольцо
Конечное кольцо в общей алгебре — это кольцо, содержащее конечное число элементов (которое называется порядком кольца). Другими словами, это (непустое) конечное множество R
Правило одного определения
05:26, 05 декабрь
Правило одного определения
Правило одного определения (One Definition Rule, ODR) — один из основных принципов языка программирования C++. Назначение ODR состоит в том, чтобы в программе не могло появиться два или более
Комментарии:
Добавить комментарий
Ваше Имя:
Ваш E-Mail: