WikiDer > Правило 90

Rule 90

Пространственно-временная диаграмма Правила 90 со случайными начальными условиями. Каждая строка пикселей представляет собой конфигурацию автомата; время идет вертикально сверху вниз.

в математический исследование клеточные автоматы, Правило 90 является элементарный клеточный автомат на основе Эксклюзивный или функция. Он состоит из одномерного массива ячеек, каждая из которых может содержать значение 0 или 1. На каждом временном шаге все значения одновременно заменяются исключительным или двух соседних значений.[1] Мартин, Одлыжко и Вольфрам (1984) назовем это «простейшим нетривиальным клеточным автоматом»,[2] и это подробно описано в Стивен Вольфрамкнига 2002 года Новый вид науки.[3]

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

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

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

Описание

Правила

В Правиле 90 значение каждой ячейки вычисляется как исключительное или двух соседних значений на предыдущем временном шаге.

Правило 90 - это элементарный клеточный автомат. Это означает, что он состоит из одномерного массива ячеек, каждая из которых содержит одно двоичное значение, 0 или 1. Присвоение значений всем ячейкам называется конфигурация. Автомат получает начальную конфигурацию, а затем проходит через другие конфигурации в последовательности дискретных временных шагов. На каждом шаге все ячейки обновляются одновременно. Предварительно заданное правило определяет новое значение каждой ячейки как функцию ее предыдущего значения и значений в двух соседних ячейках. Все ячейки подчиняются одному и тому же правилу, которое может быть задано либо в виде формулы, либо в виде таблицы правил, определяющей новое значение для каждой возможной комбинации соседних значений.[1]

В случае правила 90 новое значение каждой ячейки - это Эксклюзивный или двух соседних значений. Точно так же следующее состояние этого конкретного автомата регулируется следующей таблицей правил:[1]

текущий образец111110101100011010001000
новое состояние для центральной ячейки01011010

Именование

Название Правила 90 происходит от Стивен Вольфрамс двоично-десятичная запись для одномерных правил клеточного автомата. Чтобы вычислить обозначение для правила, объедините новые состояния в таблице правил в один двоичное число, и преобразовать число в десятичный: 010110102 = 9010.[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 можно сформировать математический лес, а ориентированный ациклический граф в котором каждый вершина имеет не более одного исходящего ребра, деревья которого совпадают с деревьями в метафоре Миллера. В лесу есть вершина для каждой пары (Икс,я) такая эта клетка Икс ненулевое время я. Вершины в момент времени 0 не имеют исходящих ребер; каждый образует корень дерева в лесу. Для каждой вершины (Икс,я) с я ненулевое, его исходящее ребро переходит в (Икс ± 1, я − 1), единственный ненулевой сосед Икс вовремя я − 1. Миллер заметил, что в этих лесах образуются треугольные «поляны», области пространственно-временной диаграммы без ненулевых ячеек, ограниченные плоским нижним краем и диагональными сторонами. Такая очистка образуется, когда последовательная последовательность ячеек становится равной нулю одновременно за один временной шаг, а затем (в метафоре дерева) ветви растут внутрь, в конечном итоге повторно покрывая ячейки последовательности.[8]

При случайных начальных условиях границы между деревьями, сформированными таким образом, сами смещаются, казалось бы, случайным образом, и деревья часто полностью отмирают. Но с помощью теории регистры сдвига он и другие смогли найти начальные условия, при которых все деревья остаются живыми навсегда, модель роста периодически повторяется, и можно гарантировать, что все вырубки останутся ограниченными по размеру.[8][9]Миллер использовал эти повторяющиеся узоры для создания дизайна гобелены. Некоторые из гобеленов Миллера изображают физические деревья; другие визуализируют автомат Правила 90, используя абстрактные треугольники.[8]

Серпинский треугольник

Серпинский треугольник генерируется Правилом 90

Пространственно-временная диаграмма Правила 90 - это график, на котором яВ строке записана конфигурация автомата на шаге я. Когда в начальном состоянии есть единственная ненулевая ячейка, эта диаграмма имеет вид Серпинский треугольник, а фрактал сформированный путем объединения треугольники в более крупные треугольники. Правила 18, 22, 26, 82, 146, 154, 210 и 218 также генерируют треугольники Серпинского из одной ячейки, однако не все они созданы полностью одинаково. Один из способов объяснить эту структуру использует тот факт, что в Правиле 90 каждая ячейка является Эксклюзивный или двух своих соседей. Потому что это эквивалентно по модулю-2, это генерирует версию по модулю 2 Треугольник Паскаля. На диаграмме стоит 1 везде, где треугольник Паскаля имеет нечетное число, и 0 везде, где треугольник Паскаля имеет четное число. Это дискретная версия треугольника Серпинского.[1][10]

Количество живых клеток в каждом ряду этого паттерна равно сила двух. в я-я строка равна 2k, куда k это количество ненулевых цифр в двоичное представление числая. Последовательность этих чисел живых клеток,

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. На любом временном шаге я в эволюции Правила состояние любой ячейки может быть вычислено как исключительное или как подмножество ячеек в начальной конфигурации. Это подмножество имеет ту же форму, что и я-й ряд треугольника Серпинского.[11]

Репликация

В треугольнике Серпинского для любого целого числа я, строки, пронумерованные кратными 2я иметь ненулевые ячейки, расположенные не менее 2я единицы друг от друга. Следовательно, из-за аддитивного свойства Правила 90, если начальная конфигурация состоит из конечного шаблона п ненулевых ячеек шириной меньше 2я, затем шагами, кратными 2я, конфигурация будет состоять из копий п по крайней мере 2я единиц от начала до начала. Это расстояние достаточно велико, чтобы копии не мешали друг другу. Количество копий такое же, как и количество ненулевых ячеек в соответствующей строке треугольника Серпинского. Таким образом, в этом правиле каждый паттерн является репликатор: он генерирует несколько своих копий, которые распределяются по конфигурации, в конечном итоге заполняя весь массив. Другие правила, включая Универсальный конструктор фон Неймана, Клеточный автомат Кодда, и Петли Лэнгтона также есть репликаторы, которые работают, неся и копируя последовательность инструкций для построения самих себя. Напротив, повторение в Правиле 90 тривиально и автоматически.[12]

Предшественники и сады Эдема

В Правиле 90 на бесконечной одномерной решетке каждая конфигурация имеет ровно четыре предшествующих конфигурации. Это связано с тем, что в предшественнике любые две последовательные ячейки могут иметь любую комбинацию состояний, но после выбора состояний этих двух ячеек существует только один согласованный выбор для состояний остальных ячеек. Следовательно, нет Эдемский сад в Правиле 90 - конфигурация без предшественников. Конфигурация Правила 90, состоящая из одной ненулевой ячейки (со всеми остальными ячейками, равными нулю) не имеет предшественников, которые имели бы конечное число ненулевых. Однако эта конфигурация не является райским садом, потому что у нее есть предшественники с бесконечно большим числом ненулевых.[13]

Тот факт, что у каждой конфигурации есть предшественник, можно резюмировать, сказав, что Правило 90 является сюръективный. Функция, которая отображает каждую конфигурацию на ее преемника, математически является сюръективной функцией. Правило 90 также не инъективный. В инъективном правиле каждые две разные конфигурации имеют разных преемников, но Правило 90 имеет пары конфигураций с одним и тем же преемником. Правило 90 предоставляет пример клеточного автомата, который является сюръективным, но не инъективным. В Теорема Эдемского сада Мура и Майхилла подразумевает, что каждый инъективный клеточный автомат должен быть сюръективным, но этот пример показывает, что обратное неверно.[13][14]

Поскольку каждая конфигурация имеет только ограниченное число предшественников, эволюция Правила 90 сохраняет энтропия любой конфигурации. В частности, если бесконечная начальная конфигурация выбирается путем выбора состояния каждой ячейки независимо случайным образом, причем каждое из двух состояний с равной вероятностью будет выбрано, то каждая последующая конфигурация может быть описана точно таким же распределением вероятностей.[2]

Эмуляция другими системами

Репликатор пасты-бабочки в HighLife, одномерные массивы которого можно использовать для имитации Правила 90

Многие другие клеточные автоматы и другие вычислительные системы способны имитировать поведение Правила 90. Например, конфигурация в правиле 90 может быть преобразована в конфигурацию другого элементарного клеточного автомата, Правило 22. Трансляция заменяет каждую ячейку Правила 90 на три. последовательные ячейки Правила 22. Все эти ячейки равны нулю, если сама ячейка Правила 90 равна нулю. Ненулевая ячейка Правила 90 преобразуется в единицу, за которой следуют два нуля. При таком преобразовании каждые шесть шагов автомата по правилу 22 имитируют один шаг автомата по правилу 90. Аналогичное прямое моделирование Правила 90 возможно также для Правил 45 и 126 элементарных клеточных автоматов, для некоторых системы перезаписи строк и системы тегов, а в некоторых двумерных клеточных автоматах, в том числе Wireworld. Правило 90 также может имитировать себя таким же образом. Если каждая ячейка конфигурации по правилу 90 заменяется парой последовательных ячеек, первая из которых содержит значение исходной ячейки, а вторая - ноль, тогда эта удвоенная конфигурация будет вести себя так же, как исходная конфигурация, на половине скорости.[15]

Известно, что различные другие клеточные автоматы поддерживают репликаторы, шаблоны, которые создают копии самих себя, и большинство из них имеют то же поведение, что и в модели роста дерева для Правила 90. Новая копия помещается по обе стороны от шаблона репликатора, пока место там пусто. Однако, если два репликатора попытаются скопировать себя в одну и ту же позицию, то пространство останется пустым. В любом случае сами репликаторы исчезают, оставляя свои копии для продолжения репликации. Стандартный пример такого поведения - рисунок "паста-бабочка" в двухмерном HighLife правило. Это правило во многом похоже на «Игру жизни» Конвея, но такого маленького репликатора в жизни не существует. Всякий раз, когда автомат поддерживает репликаторы с одним и тем же паттерном роста, можно использовать одномерные массивы репликаторов для имитации правила 90.[16] Правило 90 (для конечных рядов ячеек) также может быть смоделировано блоком генераторы двумерного Жизнеподобный клеточный автомат B36 / S125, также называемый «2x2», и поведение Правила 90 можно использовать для характеристики возможных периодов этих осцилляторов.[17]

Смотрите также

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

  1. ^ а б c d е Вольфрам, Стивен (1983), «Статистическая механика клеточных автоматов», Обзоры современной физики, 55 (3): 601–644, Bibcode:1983РвМП ... 55..601Вт, Дои:10.1103 / RevModPhys.55.601.
  2. ^ а б c Мартин, Оливье; Одлызко, Андрей М.; Вольфрам, Стивен (1984), «Алгебраические свойства клеточных автоматов», Коммуникации по математической физике, 93 (2): 219–258, Bibcode:1984CMaPh..93..219M, Дои:10.1007 / BF01223745.
  3. ^ Вольфрам, Стивен (2002), Новый вид науки, Wolfram Media. В указателе книги перечислены более 50 отдельных подтем Правила 90.
  4. ^ а б Клауссен, Йенс Кристиан; Наглер, Ян; Шустер, Хайнц Георг (2004), «сигнал Серпинского генерирует 1 ∕ж α спектры », Физический обзор E, 70: 032101, arXiv:cond-mat / 0308277, Bibcode:2004PhRvE..70c2101C, Дои:10.1103 / PhysRevE.70.032101.
  5. ^ Мисюревич, Михал; Стивенс, Джон Дж .; Томас, Дайана М. (2006), "Итерации линейных отображений над конечными полями", Линейная алгебра и ее приложения, 413 (1): 218–234, Дои:10.1016 / j.laa.2005.09.002.
  6. ^ Макинтош, Гарольд В. (1993), Предки: Комментарии Эндрю Вуэнше и Майка Лессера к «Глобальной динамике клеточных автоматов» (Addison-Wesley, 1992) (PDF), Instituto de Ciencias, Автономный университет Пуэблы.
  7. ^ Кавахарада, Аканэ (2014), «Клеточный автомат Улама и Правило 150», Математический журнал Хоккайдо, 43 (3): 361–383, Дои:10.14492 / hokmj / 1416837570, МИСТЕР 3282639: «За исключением тривиальных CA, остальные четыре линейных элементарных CA, Правило 60, Правило 90, Правило 102 и Правило 150, по существу эквивалентны Правилу 90 или Правилу 150».
  8. ^ а б c d Миллер, Дж. С. П. (1970), «Периодические леса низкорослых деревьев», Философские труды Лондонского королевского общества, Серия А, Математические и физические науки, 266 (1172): 63–111, Bibcode:1970РСПТА.266 ... 63М, Дои:10.1098 / рста.1970.0003, JSTOR 73779.
  9. ^ АпСимон, Х. Г. (1970), «Периодические леса, самые большие вырубки которых имеют размер 3», Философские труды Лондонского королевского общества, Серия А, Математические и физические науки, 266 (1172): 113–121, Bibcode:1970RSPTA.266..113A, Дои:10.1098 / рста.1970.0004, JSTOR 73780; АпСимон, Х. Г. (1970), "Периодические леса, самые большие вырубки которых имеют размер п ≥ 4", Философские труды Лондонского королевского общества, Серия А, Математические и физические науки, 266 (1538): 399–404, Bibcode:1970RSPSA.319..399A, Дои:10.1098 / rspa.1970.0185, JSTOR 73780. Аналогичный анализ периодических конфигураций в Правиле 90 также содержится в Вольфрам (2002), п. 954.
  10. ^ Вольфрам (2002)С. 25–26, 270–271, 870.
  11. ^ Kar, B.K .; Gupta, A .; Чаудхури, П. Пал (1993), "О явных выражениях в аддитивной теории клеточных автоматов", Информационные науки, 72 (1–2): 83–103, Дои:10.1016 / 0020-0255 (93) 90030-П.
  12. ^ Ваксман, Абрахам (1969), «Модель репликации», Журнал ACM, 16 (1): 178–188, Дои:10.1145/321495.321509; Аморосо, Серафино; Купер, Джеральд (1971), "Тесселяционные структуры для воспроизведения произвольных узоров", Журнал компьютерных и системных наук, 5 (5): 455–464, Дои:10.1016 / S0022-0000 (71) 80009-0. Вольфрам (1983) (Рис.33 и окружающий текст) также упоминает то же свойство, и, цитируя Ваксмана, Аморосо и Купера, он приписывает это наблюдение неопубликованной работе автора. Эдвард Фредкин в 1981 г.
  13. ^ а б Скайум, Свен (1975), «Беспорядок в Эдемском саду», Труды Американского математического общества, 50 (1): 332–336, Дои:10.1090 / S0002-9939-1975-0386350-1
  14. ^ Сатнер, Клаус (1991), "Графы Де Брейна и линейные клеточные автоматы" (PDF), Сложные системы, 5: 19–30. Вольфрам (2002)С. 959–960. Мартин, Одлыжко и Вольфрам (1984) провести аналогичный анализ предшественников того же правила для конечных наборов ячеек с периодическими граничными условиями.
  15. ^ Вольфрам (2002), стр. 269–270, 666–667, 701–702, 1117.
  16. ^ Гриффит, Дэвид (1996), «Рецепт на неделю с 1 по 7 июля: воспроизведение Скитеров», Исконная суповая кухня.
  17. ^ Джонстон, Натаниэль (2010), "The B36 / S125" 2x2 "Жизнеподобный клеточный автомат", в Адамацкий Андрей (ред.), Клеточные автоматы Game of Life, Springer-Verlag, стр. 99–114, arXiv:1203.1644, Bibcode:2010golc.book ... 99J, Дои:10.1007/978-1-84996-217-9_7.

внешняя ссылка