Код Вольфрама

Код Вольфрама — это широко используемая ^[1] система нумерации для правил одномерного клеточного автомата , введенная Стивеном Вольфрамом в статье 1983 года ^[2] и популяризированная в его книге «Новый вид науки» . ^[3]

Код основан на наблюдении, что таблица, определяющая новое состояние каждой ячейки в автомате, как функцию состояний в ее окрестности, может быть интерпретирована как k -значное число в S -арной позиционной системе счисления, где S — число состояний, которые может иметь каждая ячейка в автомате, k  = S ^{2 n  + 1} — число конфигураций окрестности, а n — радиус окрестности. Таким образом, код Wolfram для конкретного правила — это число в диапазоне от 0 до S ^{S 2 n + 1}  − 1, преобразованное из S -арной в десятичную систему счисления. Его можно вычислить следующим образом:

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

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

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

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

Наиболее распространенный пример имеет S = 2 , n = 1 и D = 1 , что дает R = 256. Количество возможных правил имеет экстремальную зависимость от размерности системы. Например, увеличение количества измерений ( D ) с 1 до 2 увеличивает количество возможных правил с 256 до 2 ⁵¹² (что составляет ~1,341×10 ¹⁵⁴ ).