Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

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

Обобщенные клеточные автоматы [ править ]

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

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

Ссылки [ править ]

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