Правило 90: различия между версиями
перевод с английского |
(нет различий)
|
Версия от 16:28, 25 сентября 2017
Правило 90 (англ. Rule 90) — это элементарный клеточный автомат, основанный на функции сложения по модулю 2 (исключающего «ИЛИ», англ. XOR). Он состоит из одномерного массива ячеек, каждая из которых содержит значение 0 или 1. Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей.[1] Правило 90 является простейшим нетривиальным клеточным автоматом.[2] Он детально описан в книге Стивена Вольфрама A New Kind of Science (с англ. — «Наука нового типа»).[3]
Для простейшей конфигурации — начальное положение которой содержит только одну живую (имеющую значение 1) ячейку — диаграмма времени-пространства имеет форму треугольника Серпинского. Поведение любой другой конфигурации может быть объяснено путём сложения по модулю 2 простейших конфигураций. В частности, любая конфигурация с конечным числом ненулевых ячеек является репликатором, который постепенно заполняет всё поле своими копиями. Если изначальная конфигурация Правила 90 случайна, то последующие — тоже. Соответствующая диграмма времени-пространства имеет много треугольных «окон» разных размеров, получающихся при постепенном заполнении ряда из нескольких нулей.
Ранние исследования Правила 90 были мотивированы гипотезой Гильбрайта — неразрешённой проблемой из теории чисел, связанной с разностями соседних простых чисел. Также с точки зрения теории чисел интересна последовательность Гулда, содержащая количество ненулевых ячеек на разных шагах в простейшей конфигурации. Её значения — это степени двойки с показателями, равными числу ненулевых цифр в двоичном представлении номеров шага (начиная нумерацию с 0).
У любой конфигурацию Правила 90 есть в точности четыре предшественника, поэтому, в отличии от многих других клеточных автоматов вроде Игры «Жизнь», у этого автомата нет сада Эдема, конфигурации без предшественников. Таким образом, Правило 90 является клеточным автоматом, который сюръективен (у каждой конфигурации есть предшественник), но не инъективен (есть конфигурации, которые приводят к одной и той же на следующем шаге), и тем самым даёт контрпример к теореме, обратной к теореме сада Эдема.
Примечания
- ↑ Wolfram, Stephen (1983), "Statistical mechanics of cellular automata", Reviews of Modern Physics, 55 (3): 601—644, Bibcode:1983RvMP...55..601W, doi:10.1103/RevModPhys.55.601.
- ↑ Martin, Olivier; Odlyzko, Andrew M.; Wolfram, Stephen (1984), "Algebraic properties of cellular automata", Communications in Mathematical Physics, 93 (2): 219—258, Bibcode:1984CMaPh..93..219M, doi:10.1007/BF01223745.
- ↑ Wolfram, Stephen (2002), A New Kind of Science, Wolfram Media. Алфавитный указатель книги перечисляет более 50 подтем, связанных с автоматом Правило 90.