WikiDer > Код Wolfram

Эта статья слишком полагается на Рекомендации к основные источники. Пожалуйста, улучшите это, добавив вторичные или третичные источники. (Апрель 2020) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

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

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

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

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

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

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

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