WikiDer > Код Wolfram

Wolfram code

Код Wolfram система именования, часто используемая для одномерных клеточный автомат правила, введенные Стивен Вольфрам в статье 1983 г.[1] и использовал в своей книге Новый вид науки.[2]

Код основан на наблюдении, что таблица, определяющая новое состояние каждой ячейки в автомате в зависимости от состояний в ее окрестности, может интерпретироваться как k-цифровой номер в S-арная позиционная система счисления, где S - количество состояний, которые может иметь каждая ячейка в автомате, k = S2п + 1 - количество конфигураций соседства, а п - радиус окрестности. Таким образом, код Вольфрама для конкретного правила представляет собой число в диапазоне от 0 до SS2п + 1 - 1, преобразовано из S-при десятичный обозначение. Его можно рассчитать следующим образом:

  1. Перечислите все S2п + 1 возможные конфигурации состояний окрестности данной ячейки.
  2. Интерпретируя каждую конфигурацию как число, как описано выше, отсортируйте их в порядке убывания номеров.
  3. Для каждой конфигурации укажите состояние, в котором данная ячейка будет в соответствии с этим правилом на следующей итерации.
  4. Снова интерпретируйте полученный список состояний как S-арное число и преобразовать это число в десятичное. Полученное десятичное число - это код Вольфрама.

Код Wolfram не определяет размер (или форму) окрестности или количество состояний - предполагается, что они известны из контекста. При использовании отдельно без такого контекста часто предполагается, что коды относятся к классу элементарные клеточные автоматы, одномерные клеточные автоматы с двумя состояниями с (смежной) трехклеточной окрестностью, которые Вольфрам подробно исследует в своей книге. Известные правила в этом классе включают Правило 30, Правило 110, и Правило 184. Правило 90 интересен еще и тем, что создает Треугольник Паскаля по модулю 2. Код этого типа с суффиксом R, например "Правило 37R", указывает клеточный автомат второго порядка с такой же структурой соседства.

Хотя в строгом смысле каждый код Wolfram в допустимом диапазоне определяет другое правило, некоторые из этих правил являются изоморфный и обычно считается эквивалентным. Например, приведенное выше правило 110 изоморфно правилам 124, 137 и 193, которые могут быть получены из оригинала путем отражения влево-вправо и перенумерации состояний. По соглашению каждый такой класс изоморфизма представлен правилом с наименьшим в нем кодовым номером. Недостатком нотации Вольфрама и, в частности, использования десятичной нотации является то, что она затрудняет просмотр таких изоморфизмов, чем некоторые альтернативные нотации. Несмотря на это, он стал стандарт де-факто способ обозначения одномерных клеточных автоматов.

Обобщенные клеточные автоматы

Количество возможных правил, р, для обобщенного клеточного автомата, в котором каждая клетка может принимать одно из S состояний, определяемых размером соседства п, в D-мерное пространство определяется:R = SS(2n + 1)D

Самый распространенный пример: S = 2, п = 1 и D = 1, давая R = 256. Количество возможных правил сильно зависит от размерности системы. Например, увеличение количества измерений (D) от 1 до 2 увеличивает количество возможных правил с 256 до 2512 (который ~1.341×10154).

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

  1. ^ Вольфрам, Стивен (июль 1983 г.). «Статистическая механика клеточных автоматов». Обзоры современной физики. 55: 601–644. Bibcode:1983РвМП ... 55..601Вт. Дои:10.1103 / RevModPhys.55.601.
  2. ^ Вольфрам, Стивен, Новый вид науки. Wolfram Media, Inc., 14 мая 2002 г. ISBN 1-57955-008-8