Введение
Элементарный клеточный автомат – клеточный автомат, представленный Стивеном Вольфрамом в 1983 году. Согласно классификации Вольфрама, правило 30 относится к классу III, демонстрируя апериодичное, хаотическое поведение. Это правило представляет особый интерес, поскольку оно генерирует сложные, кажущиеся случайными узоры из простых и чётко определенных правил. Благодаря этому Вольфрам полагает, что правило 30 и клеточные автоматы в целом могут стать ключом к пониманию того, как простые правила порождают сложные структуры и поведение в природе. Например, узор, напоминающий правило 30, встречается на раковине широко распространенного вида конусовидных улиток Conus textile. Правило 30 также использовалось в качестве генератора случайных чисел в Mathematica и было предложено в качестве возможного потокового шифра для криптографии. Правило 30 получило свое название, потому что 30 – это наименьший код Вольфрама, описывающий его набор правил (как описано ниже). Зеркальное отражение, дополнение и зеркальное дополнение правила 30 имеют коды Вольфрама 86, 135 и 149 соответственно.
the cellular automaton
Rule 30 is an elementary cellular automaton introduced by Stephen Wolfram in 1983. Using Wolfram's classification scheme, Rule 30 is a Class III rule, displaying aperiodic, chaotic behaviour. This rule is of particular interest because it produces complex, seemingly random patterns from simple, well defined rules. Because of this, Wolfram believes that Rule 30, and cellular automata in general, are the key to understanding how simple rules produce complex structures and behaviour in nature. For instance, a pattern resembling Rule 30 appears on the shell of the widespread cone snail species Conus textile. Rule 30 has also been used as a random number generator in Mathematica, and has also been proposed as a possible stream cipher for use in cryptography. Rule 30 is so named because 30 is the smallest Wolfram code which describes its rule set (as described below). The mirror image, complement, and mirror complement of Rule 30 have Wolfram codes 86, 135, and 149, respectively.
Хаос
Правило 30 соответствует строгим определениям хаоса, предложенным Девани и Кнудсоном. В частности, согласно критериям Деванея, правило 30 демонстрирует чувствительную зависимость от начальных условий (две начальные конфигурации, различающиеся лишь в небольшом количестве ячеек, быстро расходятся), его периодические конфигурации плотны в пространстве всех конфигураций в соответствии с топологией Кантора на пространстве конфигураций (существует периодическая конфигурация с любым конечным паттерном ячеек), и оно обладает свойством смешивания (для любых двух конечных паттернов ячеек существует конфигурация, содержащая один паттерн, который в конечном итоге приводит к конфигурации, содержащей другой паттерн). Согласно критериям Кнудсона, оно демонстрирует чувствительную зависимость и содержит плотную орбиту (начальная конфигурация, которая в конечном итоге отображает любой конечный паттерн ячеек). Обе эти характеристики хаотического поведения правила вытекают из более простого и легко проверяемого свойства правила 30: оно является лево-пермутативным, то есть, если две конфигурации C и D отличаются состоянием одной ячейки в позиции i, то после одного шага новые конфигурации будут отличаться в ячейке i + 1.
Генерация случайных чисел
Как видно из изображения выше, правило 30 генерирует видимую случайность, несмотря на отсутствие каких-либо разумных оснований считать входные данные случайными. Стивен Вольфрам предложил использовать его центральный столбец в качестве генератора псевдослучайных чисел (PRNG); он успешно проходит многие стандартные тесты на случайность, и Вольфрам ранее использовал это правило в продукте Mathematica для генерации случайных целых чисел. Сиппер и Томассини показали, что при использовании в качестве генератора случайных чисел правило 30 демонстрирует неудовлетворительные результаты в хи-квадрат тесте при применении ко всем столбцам правил, по сравнению с другими генераторами, основанными на клеточных автоматах. Авторы также выразили опасение, что "относительно низкие результаты, полученные для правила 30 CA, могут быть обусловлены тем, что мы рассматривали N параллельно генерируемых случайных последовательностей, а не единственную последовательность, рассматриваемую Вольфрамом".
Декоративные элементы
Железнодорожный вокзал Кембридж-Норт украшен архитектурными панелями, демонстрирующими эволюцию правила 30 (или, эквивалентно, при черно-бечной инверсии, правила 135). Архитектор описал дизайн как вдохновленный игрой «Жизнь» Конвея, другим клеточным автоматом, исследованным кембриджским математиком Джоном Хортоном Конвеем, однако он фактически не основан на этой игре.