Правило 90
В математическом исследовании автоматов клеточных правило 90 представляет собой элементарный клеточный автомат, основанный на исключающей функции или. Он состоит из одномерного массива ячеек, каждая из которых может содержать значение 0 или 1. На каждом временном шаге все значения одновременно заменяются исключающим ИЛИ двух соседних значений. [1] Мартин, Одлыжко и Вольфрам (1984) называют его «простейшим нетривиальным клеточным автоматом». [2] и это подробно описано в книге Стивена Вольфрама 2002 года «Новый вид науки» . [3]
При запуске из одной живой клетки Правило 90 имеет пространственно-временную диаграмму в форме треугольника Серпинского . Поведение любой другой конфигурации можно объяснить как суперпозицию копий этого шаблона, объединенных с помощью эксклюзивной функции или . Любая конфигурация, имеющая лишь конечное число ненулевых ячеек, становится репликатором , который в конечном итоге заполняет массив своими копиями. Когда Правило 90 запускается со случайной начальной конфигурацией, его конфигурация остается случайной на каждом временном шаге. Его пространственно-временная диаграмма образует множество треугольных «окон» разного размера, закономерностей, которые образуются, когда последовательный ряд ячеек одновременно становится нулевым, а затем ячейки со значением 1 постепенно перемещаются в этот ряд с обоих концов.
Некоторые из самых ранних исследований Правила 90 были проведены в связи с нерешенной проблемой теории чисел — гипотезой Гилбрита — о разнице последовательных простых чисел .Это правило также связано с теорией чисел другим способом — через последовательность Гулда . Эта последовательность подсчитывает количество ненулевых ячеек на каждом временном шаге после запуска Правила 90 с одной живой ячейкой.Его значения представляют собой степени двойки с показателями, равными количеству ненулевых цифр в двоичном представлении номера шага. Другие применения Правила 90 включали дизайн гобеленов .
Каждая конфигурация Правила 90 имеет ровно четыре предшественника — другие конфигурации, которые образуют данную конфигурацию после одного шага. Поэтому, в отличие от многих других клеточных автоматов, таких как «Игра жизни» Конвея , Правило 90 не имеет райского сада — конфигурации, не имеющей предшественников. Он представляет собой пример клеточного автомата, который является сюръективным (каждая конфигурация имеет предшественника), но не инъективным (он имеет наборы из более чем одной конфигурации с одним и тем же преемником). следует Из теоремы о райском саду , что правило 90 локально инъективно (все конфигурации с одним и тем же преемником изменяются на бесконечном числе ячеек).
Описание [ править ]
Правила [ править ]
Правило 90 — это элементарный клеточный автомат . Это означает, что он состоит из одномерного массива ячеек, каждая из которых содержит одно двоичное значение: 0 или 1. Присвоение значений всем ячейкам называется конфигурацией . Автомату задается начальная конфигурация, а затем он проходит через другие конфигурации в последовательности шагов дискретного времени. На каждом этапе все ячейки обновляются одновременно. Предварительно заданное правило определяет новое значение каждой ячейки как функцию ее предыдущего значения и значений в двух соседних ячейках. Все ячейки подчиняются одному и тому же правилу, которое может быть задано либо в виде формулы, либо в виде таблицы правил, определяющей новое значение для каждой возможной комбинации соседних значений. [1]
В случае Правила 90 новое значение каждой ячейки является исключительным из двух соседних значений. Аналогично, следующее состояние этого конкретного автомата определяется следующей таблицей правил: [1]
| текущий шаблон | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| новое состояние центральной ячейки | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
Именование [ править ]
Название Правила 90 происходит от Стивена Вольфрама для двоично-десятичного обозначения одномерных правил клеточного автомата. Чтобы вычислить обозначение правила, объедините новые состояния в таблице правил в одно двоичное число и преобразуйте это число в десятичное : 01011010 2 = 90 10 . [1] Правило 90 также называют автоматом Серпинского из-за характерной формы треугольника Серпинского , который оно порождает: [4] и клеточный автомат Мартина-Одлизко-Вольфрама после ранних исследований Оливье Мартина, Эндрю М. Одлизко и Стивена Вольфрама ( 1984 ). этого автомата [5]
Свойства [ править ]
, суперпозиция разложение и Аддитивность
Конфигурацию в Правиле 90 можно разделить на два подмножества ячеек, которые не взаимодействуют друг с другом. Одно из этих двух подмножеств состоит из ячеек в четных позициях с четными временными шагами и ячеек в нечетных позициях с нечетными временными шагами. Другое подмножество состоит из ячеек в четных позициях с нечетными временными шагами и ячеек в нечетных позициях с четными временными шагами. Каждое из этих двух подмножеств можно рассматривать как клеточный автомат, состоящий только из половины ячеек. [6] Правило для автомата внутри каждого из этих подмножеств эквивалентно (за исключением сдвига на половину ячейки за такт) другому элементарному клеточному автомату , Правилу 102 , в котором новое состояние каждой ячейки является исключительным или ее старым состоянием. и его правый сосед. То есть поведение Правила 90 по сути такое же, как поведение двух чередующихся копий Правила 102. [7]
Правило 90 и Правило 102 называются аддитивными клеточными автоматами . Это означает, что если два начальных состояния объединяются путем вычисления исключающего или каждого из их состояний, то их последующие конфигурации будут объединяться таким же образом. В более общем смысле, можно разделить любую конфигурацию Правила 90 на два подмножества с непересекающимися ненулевыми ячейками, развивать два подмножества отдельно и вычислять каждую последующую конфигурацию исходного автомата как исключительную или конфигурацию на одинаковых временных шагах двух подмножеств. . [2]
Низкорослые деревья и треугольные поляны [ править ]
Автомат Правила 90 (в его эквивалентной форме на одном из двух независимых подмножеств чередующихся ячеек) был исследован в начале 1970-х годов в попытке получить дополнительное понимание гипотезы Гилбрита о различиях последовательных простых чисел . В треугольнике чисел, сгенерированном из простых чисел путем многократного применения оператора прямой разности , оказывается, что большинство значений равны либо 0, либо 2. В частности, гипотеза Гилбрита утверждает, что все самые левые значения в каждой строке этого треугольника равны 0 или 2. Если все смежные подпоследовательности значений в одной строке треугольника равны 0 или 2, то Правило 90 можно использовать для определения соответствующей подпоследовательности в следующей строке. Миллер (1970) объяснил это правило метафорой роста деревьев в лесу, озаглавив свою статью на тему «Периодические леса низкорослых деревьев». В этой метафоре дерево начинает расти в каждой позиции исходной конфигурации, значение которой равно 1, и затем этот лес деревьев растет одновременно, достигая новой высоты над землей на каждом временном шаге. Каждая ненулевая ячейка на каждом временном шаге представляет позицию, которую занимает растущая ветвь дерева. На каждом последующем временном шаге ветвь может вырасти в одну из двух ячеек над ней слева и справа только тогда, когда нет другой ветви, конкурирующей за ту же ячейку. Лес деревьев, растущий по этим правилам, ведет себя точно так же, как Правило 90. [8]
Из любой начальной конфигурации Правила 90 можно сформировать математический лес — ориентированный ациклический граф , в котором каждая вершина имеет не более одного исходящего ребра, деревья которого такие же, как деревья в метафоре Миллера. В лесу есть вершина для каждой пары ( x , i ) такая, что ячейка x не равна нулю в момент i . Вершины в момент времени 0 не имеют исходящих ребер; каждый из них образует корень дерева в лесу. Для каждой вершины ( x , i ) с i ненулевым, ее исходящее ребро переходит в ( x ± 1, i − 1) , единственный ненулевой сосед x на временном шаге i − 1 . Миллер заметил, что в этих лесах образуются треугольные «поляны», области диаграммы времени-пространства без ненулевых ячеек, ограниченные плоским нижним краем и диагональными сторонами. Такая очистка образуется, когда последовательная последовательность ячеек одновременно за один временной шаг становится нулевой, а затем (в метафоре дерева) ветви растут внутрь, в конечном итоге заново покрывая ячейки последовательности. [8]
При случайных начальных условиях границы между образовавшимися таким образом деревьями сами смещаются, казалось бы, случайным образом, и деревья часто вообще вымирают. Но с помощью теории сдвиговых регистров он и другие смогли найти начальные условия, при которых все деревья остаются живыми навсегда, закономерность роста периодически повторяется, и все поляны могут быть гарантированно останутся ограниченными по размеру. [8] [9] Миллер использовал эти повторяющиеся узоры для формирования рисунков гобеленов . На некоторых гобеленах Миллера изображены настоящие деревья; другие визуализируют автомат по Правилу 90, используя абстрактные узоры из треугольников. [8]
Треугольник Серпинского [ править ]
Временно-пространственная диаграмма Правила 90 представляет собой график, на котором i -я строка записывает конфигурацию автомата на шаге i . Когда исходное состояние имеет одну ненулевую ячейку, эта диаграмма имеет вид треугольника Серпинского , фрактала, образованного путем объединения треугольников в более крупные треугольники. Правила 18, 22, 26, 82, 146, 154, 210 и 218 также генерируют треугольники Серпинского из одной ячейки, однако не все они создаются совершенно одинаково. Одним из способов объяснения этой структуры является тот факт, что в Правиле 90 каждая ячейка является единственной из двух своих соседей. Поскольку это эквивалентно сложению по модулю -2, это генерирует версию треугольника Паскаля по модулю 2 . На диаграмме стоит 1, если треугольник Паскаля имеет нечетное число , и 0, если треугольник Паскаля имеет четное число . Это дискретная версия треугольника Серпинского. [1] [10]
Количество живых клеток в каждой строке этого шаблона равно степени двойки . В i -й строке оно равно 2 к , где k — количество ненулевых цифр в двоичном представлении числа i . Последовательность этих чисел живых клеток,
- 1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, ... (последовательность A001316 в OEIS )
известна как последовательность Гулда .Единственная живая ячейка начальной конфигурации представляет собой пилообразный узор . Это означает, что на некоторых временных шагах количество живых клеток становится сколь угодно большим, а на других они бесконечно часто возвращаются только к двум живым клеткам.Скорость роста этой модели имеет характерную растущую пилообразную форму волны , которую можно использовать для распознавания физических процессов, которые ведут себя аналогично Правилу 90. [4]
Треугольник Серпинского также встречается более тонким образом в эволюции любой конфигурации в Правиле 90. На любом временном шаге i в эволюции Правила состояние любой ячейки может быть рассчитано как исключительная или подмножество ячеек в первоначальная конфигурация. Это подмножество имеет ту же форму, что и i -я строка треугольника Серпинского. [11]
Репликация [ править ]
В треугольнике Серпинского для любого целого числа i строки с номерами, кратными 2, я иметь ненулевые ячейки, расположенные как минимум на расстоянии 2 я единицы отдельно. Следовательно, из-за аддитивного свойства Правила 90, если исходная конфигурация состоит из конечного шаблона P ненулевых ячеек шириной менее 2 я , затем шагами, кратными 2 я , конфигурация будет состоять из копий P, расположенных на расстоянии не менее 2 я единиц от начала до начала. Это расстояние достаточно велико, чтобы копии не мешали друг другу. Количество копий совпадает с количеством ненулевых ячеек в соответствующей строке треугольника Серпинского. Таким образом, в этом правиле каждый шаблон является репликатором : он генерирует множество своих копий, которые распространяются по конфигурации, в конечном итоге заполняя весь массив. Другие правила, включая универсальный конструктор фон Неймана , клеточный автомат Кодда и циклы Лэнгтона, также имеют репликаторы, которые работают, перенося и копируя последовательность инструкций для построения самих себя. Напротив, повторение в Правиле 90 является тривиальным и автоматическим. [12]
Эдемские Предшественники и сады
В правиле 90 на бесконечной одномерной решетке каждая конфигурация имеет ровно четыре конфигурации-предшественника. Это связано с тем, что в предшественнике любые две последовательные ячейки могут иметь любую комбинацию состояний, но как только состояния этих двух ячеек выбраны, существует только один последовательный выбор для состояний остальных ячеек. Следовательно, в Правиле 90 нет Эдемского сада , конфигурации, не имеющей предшественников. Конфигурация Правила 90, состоящая из одной ненулевой ячейки (все остальные ячейки равны нулю), не имеет предшественников, которые имеют конечное число ненулевых значений. Однако эта конфигурация не является райским садом, поскольку у нее есть предшественники с бесконечным количеством ненулевых значений. [13]
Тот факт, что каждая конфигурация имеет предшественника, можно резюмировать, сказав, что Правило 90 сюръективно . Функция, которая сопоставляет каждую конфигурацию с ее преемником, математически является сюръективной функцией. Правило 90 также не является инъективным . В инъективном правиле каждые две разные конфигурации имеют разных преемников, но правило 90 имеет пары конфигураций с одним и тем же преемником. Правило 90 представляет собой пример клеточного автомата, который является сюръективным, но не инъективным. подразумевает Теорема Мура и Майхилла о Эдемском саду , что каждый инъективный клеточный автомат должен быть сюръективным, но этот пример показывает, что обратное неверно. [13] [14]
Поскольку каждая конфигурация имеет лишь ограниченное число предшественников, эволюция Правила 90 сохраняет энтропию любой конфигурации. В частности, если бесконечная начальная конфигурация выбирается путем выбора состояния каждой ячейки независимо случайным образом, причем каждое из двух состояний выбрано с равной вероятностью, то каждая последующая конфигурация может быть описана точно таким же распределением вероятностей. [2]
Эмуляция другими системами [ править ]
Многие другие клеточные автоматы и другие вычислительные системы способны имитировать поведение Правила 90. Например, конфигурация в правиле 90 может быть преобразована в конфигурацию другого элементарного клеточного автомата по Правилу 22. При трансляции каждая ячейка Правила 90 заменяется тремя последовательные ячейки Правила 22. Все эти ячейки равны нулю, если ячейка Правила 90 сама равна нулю. Ненулевая ячейка Правила 90 преобразуется в единицу, за которой следуют два нуля. При таком преобразовании каждые шесть шагов автомата по Правилу 22 имитируют один шаг автомата по Правилу 90. Подобное прямое моделирование Правила 90 также возможно для элементарных клеточных автоматов Правило 45 и Правило 126, для некоторых систем переписывания строк и систем тегов , а также для некоторых двумерных клеточных автоматов, включая Wireworld . Правило 90 также может моделировать себя таким же образом. Если каждая ячейка конфигурации Правила 90 заменяется парой последовательных ячеек, первая из которых содержит значение исходной ячейки, а вторая — ноль, то эта удвоенная конфигурация будет вести себя так же, как и исходная конфигурация, но на половине скорости. [15]
Известно, что различные другие клеточные автоматы поддерживают репликаторы, шаблоны, которые создают копии самих себя, и большинство из них имеют то же поведение, что и в модели роста дерева для Правила 90. Новая копия помещается по обе стороны от шаблона репликатора, пока место там пустое. Однако если два репликатора попытаются скопировать себя в одну и ту же позицию, то пространство останется пустым. В любом случае сами репликаторы исчезают, оставляя свои копии для продолжения репликации. Стандартным примером такого поведения является узор «макароны-бабочки» в двумерном правиле HighLife . Это правило во многом похоже на игру «Жизнь» Конвея, но в «Жизни» не существует такого маленького репликатора. Всякий раз, когда автомат поддерживает репликаторы с одинаковой схемой роста, для имитации Правила 90 можно использовать одномерные массивы репликаторов. [16] Правило 90 (на конечных рядах ячеек) также можно моделировать с помощью блочных генераторов двумерного клеточного автомата Life-like B36/S125, также называемого «2x2», а поведение Правила 90 можно использовать для характеристики возможных периоды этих осцилляторов. [17]
См. также [ править ]
- Другие элементарные клеточные автоматы: Правило 30 , Правило 110 и Правило 184.
Ссылки [ править ]
- ^ Jump up to: Перейти обратно: а б с д и Вольфрам, Стивен (1983), «Статистическая механика клеточных автоматов» , Reviews of Modern Physics , 55 (3): 601–644, Бибкод : 1983RvMP...55..601W , doi : 10.1103/RevModPhys.55.601 .
- ^ Jump up to: Перейти обратно: а б с Мартин, Оливье; Одлизко, Андрей М .; Вольфрам, Стивен (1984), «Алгебраические свойства клеточных автоматов» , Communications in Mathematical Physics , 93 (2): 219–258, Bibcode : 1984CMaPh..93..219M , doi : 10.1007/BF01223745 , S2CID 6900060 .
- ^ Вольфрам, Стивен (2002), Новый вид науки , Wolfram Media . В указателе книги перечислено более 50 различных подтем Правила 90.
- ^ Jump up to: Перейти обратно: а б Клауссен, Йенс Кристиан; Наглер, Ян; Шустер, Хайнц Георг (2004), «Сигнал Серпинского генерирует 1/ f а Spectrums", Physical Review E , 70 (3): 032101, arXiv : cond-mat/0308277 , Bibcode : 2004PhRvE..70c2101C , doi : 10.1103/PhysRevE.70.032101 , PMID 15524560 , S2CID 39929 111 .
- ^ Мисюревич, Михал; Стивенс, Джон Г.; Томас, Диана М. (2006), «Итерации линейных карт над конечными полями», Линейная алгебра и ее приложения , 413 (1): 218–234, doi : 10.1016/j.laa.2005.09.002 .
- ^ Макинтош, Гарольд В. (1993), Предки: Комментарии к «Глобальной динамике клеточных автоматов» Эндрю Вуэнше и Майка Лессера (Аддисон-Уэсли, 1992) (PDF) , Instituto de Ciencias, Автономный университет Пуэблы .
- ^ Кавахарада, Аканэ (2014), «Клеточный автомат Улама и правило 150», Hokkaido Mathematical Journal , 43 (3): 361–383, doi : 10.14492/hokmj/1416837570 , MR 3282639 : «За исключением тривиальных CA, остальные четыре линейных элементарных CA, Правило 60, Правило 90, Правило 102 и Правило 150, по существу эквивалентны Правилу 90 или Правилу 150».
- ^ Jump up to: Перейти обратно: а б с д Миллер, JCP (1970), «Периодические леса низкорослых деревьев», Philosophical Transactions of the the Royal Society of London , Series A, Mathematical and Physical Sciences, 266 (1172): 63–111, Бибкод : 1970RSPTA.266...63M , doi : 10.1098/rsta.1970.0003 , JSTOR 73779 , S2CID 123330469 .
- ^ Апсаймон, Х.Г. (1970), «Периодические леса, самые крупные поляны которых имеют размер 3», Philosophical Transactions of the the Royal Society of London , Series A, Mathematical and Physical Sciences, 266 (1172): 113–121, Bibcode : 1970RSPTA.266 ..113A , doi : 10.1098/rsta.1970.0004 , JSTOR 73780 , S2CID 121067116 ; Апсаймон, Х.Г. (1970), «Периодические леса, самые большие поляны которых имеют размер n ≥ 4», Philosophical Transactions of the the Royal Society of London , Series A, Mathematical and Physical Sciences, 266 (1538): 399–404, Bibcode : 1970RSPSA .319..399A , doi : 10.1098/rspa.1970.0185 , JSTOR 73780 , S2CID 119435085 . Подобный анализ периодических конфигураций в Правиле 90 также содержится в Wolfram (2002) , с. 954.
- ^ Вольфрам (2002) , стр. 25–26, 270–271, 870.
- ^ Кар, БК; Гупта, А.; Чаудхури, П. Пал (1993), «О явных выражениях в аддитивной теории клеточных автоматов», Information Sciences , 72 (1–2): 83–103, doi : 10.1016/0020-0255(93)90030-P .
- ^ Ваксман, Абрахам (1969), «Модель репликации», Журнал ACM , 16 (1): 178–188, doi : 10.1145/321495.321509 , S2CID 14547972 ; Аморосо, Серафино; Купер, Джеральд (1971), «Структуры тесселяции для воспроизведения произвольных шаблонов», Journal of Computer and System Sciences , 5 (5): 455–464, doi : 10.1016/S0022-0000(71)80009-0 . Вольфрам (1983) (рис. 33 и окружающий текст) также упоминает то же свойство и, помимо цитирования Ваксмана, Аморосо и Купера, приписывает это наблюдение неопубликованной работе Эдварда Фредкина в 1981 году.
- ^ Jump up to: Перейти обратно: а б Скюм, Свен (1975), «Путаница в райском саду», Труды Американского математического общества , 50 (1): 332–336, doi : 10.1090/S0002-9939-1975-0386350-1
- ^ Сатнер, Клаус (1991), «Графы Де Брёйна и линейные клеточные автоматы» (PDF) , Complex Systems , 5 : 19–30 . Вольфрам (2002) , стр. 959–960. Мартин, Одлизко и Вольфрам (1984) проводят аналогичный анализ предшественников того же правила для конечных наборов ячеек с периодическими граничными условиями.
- ^ Вольфрам (2002) , стр. 269–270, 666–667, 701–702, 1117.
- ^ Гриффит, Дэвид (1996), «Рецепт на неделю с 1 по 7 июля: репликация скитеров», « Первобытная суповая кухня » .
- ^ Джонстон, Натаниэль (2010), «Живой клеточный автомат B36/S125 «2x2», в Адамацки, Эндрю (редактор), Game of Life Cellular Automata , Springer-Verlag, стр. 99–114, arXiv : 1203.1644 , Bibcode : 2010golc.book...99J , doi : 10.1007/978-1-84996-217-9_7 , S2CID 41344677 .