Правило 30

Раковина моллюска Conus textile, пятна окраски которой очень похожи на узор, порождаемый по правилу 30.

Пра́вило 30 (англ. Rule 30) — элементарный клеточный автомат, то есть одномерный клеточный автомат с двумя состояниями (0 и 1), впервые описанный Стивеном Вольфрамом в 1983 году. Стивен Вольфрам говорит, что «это его самое любимое правило», и подробно описывает его в своей книге «A New Kind of Science». Из четырёх типов поведения, описанных в этой книге, Правило 30 обладает классом поведения III, показывая апериодическое, хаотическое поведение.

Правило представляет интерес, потому что оно порождает сложные, во многих отношениях случайные структуры из простых, чётко определенных правил. Вольфрам полагает, что клеточные автоматы в целом и Правило 30 в частности — ключ к пониманию того, как простые правила могут порождать сложные структуры и различное сложное поведение разных природных объектов. Например, структуру, похожую на порождаемую Правилом 30, можно найти на раковине широко распространённого тропического моллюска Conus textile. Правило 30 также используется как генератор псевдослучайных чисел (ГПСЧ) в продукте Wolfram Research — Mathematica. Также это правило было предложено для использования как шифратор последовательностей в криптографии.

Однако M. Sipper и M. Tomassini показали, что как ГПСЧ Правило 30 плохо проходит тест на критерий согласия Пирсона (критерий χ²) в сравнении с другими псевдослучайными последовательностями, которые были получены при помощи других клеточных автоматов.

Правило 30 так называется, потому что 30 — наименьший код описания правила поведения клеточных автоматов по Вольфраму, предложенного им в 1983 г. Если записать код правила в двоичном виде, то зеркальное отражение кода правила, инверсия битов кода и зеркальное отображение с инверсией битов имеют в десятичной системе счисления коды 120, 225 и 135 соответственно.

Описание правила

Рассматривается бесконечный одномерный массив ячеек (клеток) клеточного автомата с двумя возможными состояниями. Каждая из клеток имеет начальное состояние. В дискретные моменты времени каждая клетка изменяет своё состояние, причем это состояние зависит от предыдущего состояния этой ячейки и предыдущего состояния двух соседних ячеек — клеток-соседей. Для Правила 30 в таблице даны правила перехода центральной клетки триады в следующее состояние, и для сравнения приведены Правила 120, 225 и 135.

Текущее состояние трёх соседних клеток	111	110	101	100	011	010	001	000
по Правилу 30	0	0	0	1	1	1	1	0
по Правилу 120	0	1	1	1	1	0	0	0
по Правилу 225	1	1	1	0	0	0	0	1
по Правилу 135	1	0	0	0	0	1	1	1

Двоичные числа 11110₂ = 30₁₀, 1111000₂ = 120₁₀, 11100001₂ = 225₁₀, 10000111₂ = 135₁₀, именно поэтому эти правила, по Вольфраму, называют правилами 30, 120, 225 и 135 соответственно.

Структура и свойства

При задании различных начальных состояний клеток Правило 30 порождает разные эволюции последующих поколений клеток.

Для примера приведена эволюция по Правилу 30, начальное состояние которого только одна чёрная клетка, окруженная белыми клетками. (Принято, что чёрная клетка отвечает единичному состоянию клетки по таблице).

Эволюция одной единичной клетки во времени по Правилу 30

На этом изображении по вертикальной оси отложено время, каждый горизонтальный слой отражает состояние всех ячеек клеточного автомата поколения во время эволюции по Правилу 30. На изображении можно заметить несколько особенностей, таких как частое появление белых треугольников разных размеров, что напоминает по форме пятна на раковине моллюска и явную регулярную структуру в левой части изображения. Тем не менее, общая структура рисунка не поддаётся общему регулярному описанию. Количество черных клеток $N$ в последующих поколениях эволюции автоматов есть последовательность:

1, 3, 3, 6, 4, 9, 5, 12, 7, 12, 11, 14, 12, 19, 13, 22, 15, 19, … последовательность A070952 в OEIS

и приблизительно нарастает как $n$ — номер поколения.

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

Правило 30 выдает случайные структуры на многих наборах начальных условий. Однако существует и бесконечное количество векторов начальных условий, порождающих в эволюции периодические структуры. Тривиальный пример — вектор начальных условий, состоящий только из белых клеток (0). Менее тривиальный пример, найденный Мэтью Куком — любая бесконечная последовательность, состоящая из повторений шаблона 00001000111000, возможно, разделенных шестью единицами. Ещё больше таких шаблонов было найдено Frans Faase, они представлены здесь Архивная копия от 8 августа 2013 на Wayback Machine.

Детерминированный хаос

Вольфрам предположил хаотичность эволюции по Правилу 30, основываясь, в основном, на её внешнем графическом виде. Однако позже было показано, что применение Правила 30 удовлетворяет более строгим определениям хаоса, сформулированным Devaney и Knudson. В соответствии с критерием Devaney, Правило 30 демонстрирует эффект бабочки — (если задать 2 начальных состояния, различающиеся, например, только одним битом, то отдалённые многими поколениями потомки этих 2 состояний будут совершенно различные), периодические конфигурации плотны в пространстве всех конфигураций топологии Кантора. Также, Правило 30 обладает свойством перемешивания. В соответствии с критерием Knudson, это показывает чувствительность к начальным условиям и плотность орбит процесса (любая конфигурация в итоге приводит к возникновению всех возможных конечных конфигураций клеток). Обе этих характеристики хаотичного поведения эволюции по Правилу 30 следуют из свойства Правила 30, которое легко проверить: если две конфигурации C и B различаются на одну клетку в позиции i, тогда после одного шага новые конфигурации будут различаться в клетке i + 1.

Галерея

• 
  Начальные шаги эволюции Правила 30
• 
  2000 шагов эволюции Правила 30
• 
  Примерно 15000 шагов эволюции Правила 30
• 
  Периодические структуры при эволюции
• 
  Эволюция при случайных начальных условиях

Ссылки

• Rule 30: Wolfram’s Pseudo-random Bit Generator Архивная копия от 11 сентября 2019 на Wayback Machine. Recipe 32 at David Griffeath's Primordial Soup Kitchen.
• Weisstein, Eric W. Rule 30 (англ.) на сайте Wolfram MathWorld.
• Repeating Rule 30 patterns Архивная копия от 8 августа 2013 на Wayback Machine. Список начальных условий, результатом эволюции которых являются повторяющиеся последовательности. Frans Faase, 2003.
• Paving Mosaic Fractal Архивная копия от 10 мая 2012 на Wayback Machine. Базовая информация о структуре Правила 30 от Olivier Schmidt-Chevalier.
• Конференция TED Talk в феврале 2010 Архивная копия от 16 мая 2012 на Wayback Machine. Стивен Вольфрам рассказывает о теории вычислимых знаний, Правиле 30 и многом другом.
• The Wolram Rule 30 Prizes Архивная копия от 4 октября 2019 на Wayback Machine. Несколько вопросов о свойствах правила 30, за решение которых Вольфрам назначил премии.

См. также

• Теория хаоса
• Правило 110
• Правило 184
• Циклический клеточный автомат