| dbo:abstract
|
- In the mathematical study of cellular automata, Rule 90 is an elementary cellular automaton based on the exclusive or function. It consists of a one-dimensional array of cells, each of which can hold either a 0 or a 1 value. In each time step all values are simultaneously replaced by the exclusive or of their two neighboring values. call it "the simplest non-trivial cellular automaton", and it is described extensively in Stephen Wolfram's 2002 book A New Kind of Science. When started from a single live cell, Rule 90 has a time-space diagram in the form of a Sierpiński triangle. The behavior of any other configuration can be explained as a superposition of copies of this pattern, combined using the exclusive or function. Any configuration with only finitely many nonzero cells becomes a replicator that eventually fills the array with copies of itself. When Rule 90 is started from a random initial configuration, its configuration remains random at each time step. Its time-space diagram forms many triangular "windows" of different sizes, patterns that form when a consecutive row of cells becomes simultaneously zero and then cells with value 1 gradually move into this row from both ends. Some of the earliest studies of Rule 90 were made in connection with an unsolved problem in number theory, Gilbreath's conjecture, on the differences of consecutive prime numbers.This rule is also connected to number theory in a different way, via Gould's sequence. This sequence counts the number of nonzero cells in each time step after starting Rule 90 with a single live cell.Its values are powers of two, with exponents equal to the number of nonzero digits in the binary representation of the step number. Other applications of Rule 90 have included the design of tapestries. Every configuration of Rule 90 has exactly four predecessors, other configurations that form the given configuration after a single step. Therefore, in contrast to many other cellular automata such as Conway's Game of Life, Rule 90 has no Garden of Eden, a configuration with no predecessors. It provides an example of a cellular automaton that is surjective (each configuration has a predecessor) but not injective (it has sets of more than one configuration with the same successor). It follows from the Garden of Eden theorem that Rule 90 is locally injective (all configurations with the same successor vary at an infinite number of cells). (en)
- Правило 90 (англ. Rule 90) — это элементарный клеточный автомат, то есть одномерный клеточный автомат с двумя состояниями, основанный на функции сложения по модулю 2 (исключающего «ИЛИ», англ. XOR).Наименование «Правило 90» определяется кодом Вольфрама. Автомат состоит из одномерного массива ячеек, каждая из которых содержит значение 0 («пуста», «мертва») или 1 («заполнена», «жива»). Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей. Правило 90 является простейшим нетривиальным клеточным автоматом. Он детально описан в книге Стивена Вольфрама A New Kind of Science (с англ. — «Наука нового типа»). Для простейшей конфигурации — начальное положение которой содержит только одну живую ячейку — диаграмма времени-пространства имеет форму треугольника Серпинского. Поведение любой другой конфигурации может быть объяснено путём сложения по модулю 2 простейших конфигураций. В частности, любая конфигурация с конечным числом ненулевых ячеек является репликатором, который постепенно заполняет всё поле своими копиями. Если изначальная конфигурация Правила 90 случайна, то последующие — тоже. Соответствующая диграмма времени-пространства имеет много треугольных «окон» разных размеров, получающихся при постепенном заполнении ряда из нескольких нулей. Ранние исследования Правила 90 были мотивированы гипотезой Гильбрайта — неразрешённой проблемой из теории чисел, связанной с разностями соседних простых чисел. Также с точки зрения теории чисел интересна , содержащая количество ненулевых ячеек на разных шагах в простейшей конфигурации. Её значения — это степени двойки с показателями, равными числу ненулевых цифр в двоичном представлении номеров шага (начиная нумерацию с 0). У любой конфигурации Правила 90 есть в точности четыре предшественника, поэтому, в отличие от многих других клеточных автоматов вроде Игры «Жизнь», у этого автомата нет сада Эдема, конфигурации без предшественников. Таким образом, Правило 90 является клеточным автоматом, который сюръективен (у каждой конфигурации есть предшественник), но не инъективен (есть конфигурации, которые приводят к одной и той же на следующем шаге), и тем самым даёт контрпример к теореме, обратной к теореме сада Эдема. (ru)
|
| rdfs:comment
|
- In the mathematical study of cellular automata, Rule 90 is an elementary cellular automaton based on the exclusive or function. It consists of a one-dimensional array of cells, each of which can hold either a 0 or a 1 value. In each time step all values are simultaneously replaced by the exclusive or of their two neighboring values. call it "the simplest non-trivial cellular automaton", and it is described extensively in Stephen Wolfram's 2002 book A New Kind of Science. (en)
- Правило 90 (англ. Rule 90) — это элементарный клеточный автомат, то есть одномерный клеточный автомат с двумя состояниями, основанный на функции сложения по модулю 2 (исключающего «ИЛИ», англ. XOR).Наименование «Правило 90» определяется кодом Вольфрама. (ru)
|
