Правило 30

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Раковина моллюска Conus textile, пятна окраски которой очень похожи на узор, порождаемый по правилу 30[1].

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

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

Однако, 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

Двоичные числа 111102 = 3010, 11110002 = 12010, 111000012 = 22510, 100001112 = 13510, именно поэтому, эти правила, по Вольфраму, называют правилами 30, 120, 225 и 135 соответственно.

Структура и свойства[править | править вики-текст]

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

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

CA rule30s.png
Эволюция одной единичной клетки во времени по Правилу 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, они представленны здесь.

Детерминированный хаос[править | править вики-текст]

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

Галерея[править | править вики-текст]

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Stephen Coombes. The Geometry and Pigmentation of Seashells. www.maths.nottingham.ac.uk. University of Nottingham (February 2009). Проверено 10 апреля 2013.
  2. Wolfram, S. (1983). «Statistical mechanics of cellular automata». Rev. Mod. Phys. 55 (3): 601–644. DOI:10.1103/RevModPhys.55.601. Bibcode:1983RvMP...55..601W.
  3. Random Number Generation. Wolfram Mathematica 8 Documentation. Проверено 31 декабря 2011. Архивировано из первоисточника 2 сентября 2013.
  4. Wolfram, S. (1985). "Cryptography with cellular automata". Proceedings of Advances in Cryptology - CRYPTO '85: 429, Lecture Notes in Computer Science 218, Springer-Verlag. . См. также: Meier, Willi; Staffelbach, Othmar (1991). "Analysis of pseudo random sequences generated by cellular automata". Advances in Cryptology: Proc. Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT '91: 186, Lecture Notes in Computer Science 547, Springer-Verlag. 
  5. (2000) «Investigating topological chaos by elementary cellular automata dynamics». Theoretical Computer Science 244 (1–2): 219–241. DOI:10.1016/S0304-3975(98)00345-4.