Правило 30 - это элементарный клеточный автомат, введенный Стивеном Вольфрамом в 1983 году. [2] Используя схему классификации Вольфрама , Правило 30 является правилом класса III, демонстрирующим апериодическое, хаотическое поведение.
Это правило представляет особый интерес, поскольку оно создает сложные, на первый взгляд случайные шаблоны из простых, четко определенных правил. По этой причине Вольфрам считает, что Правило 30 и клеточные автоматы в целом являются ключом к пониманию того, как простые правила создают сложные структуры и поведение в природе. Например, узор, напоминающий Правило 30, появляется на раковине широко распространенного вида конусообразных улиток Conus Textile . Правило 30 была также использована в качестве генератора случайных чисел в Mathematica , [3] , а также была предложена в качестве возможного потокового шифра для использования в криптографии . [4] [5]
Правило 30 названо так потому, что 30 - это наименьший код Wolfram, который описывает свой набор правил (как описано ниже). Зеркальное отображение, дополнение и зеркальное дополнение правила 30 имеют коды Вольфрама 86, 135 и 149 соответственно.
Набор правил
Во всех элементарных клеточных автоматах Вольфрама рассматривается бесконечный одномерный массив ячеек клеточного автомата только с двумя состояниями, причем каждая ячейка находится в некотором начальном состоянии. Через дискретные промежутки времени каждая ячейка спонтанно меняет состояние в зависимости от своего текущего состояния и состояния двух своих соседей. Для Правила 30 набор правил, который управляет следующим состоянием автомата:
текущий образец | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
---|---|---|---|---|---|---|---|---|
новое состояние для центральной ячейки | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
Соответствующая формула: [left_cell XOR (central_cell OR right_cell)]. Это называется Правилом 30 , так как в двоичном , 00011110 2 = 30.
На следующей диаграмме показан созданный узор с ячейками, окрашенными в соответствии с предыдущим состоянием их соседства. Более темные цвета представляют собой «1», а более светлые - «0». Время увеличивается вниз по вертикальной оси.
Структура и свойства
Следующий шаблон возникает из начального состояния, в котором одна ячейка с состоянием 1 (показанная черным) окружена ячейками с состоянием 0 (белые).
Правило 30 клеточный автомат
Здесь вертикальная ось представляет время, а любое горизонтальное поперечное сечение изображения представляет состояние всех ячеек в массиве в определенной точке эволюции паттерна. В этой структуре присутствует несколько мотивов, таких как частое появление белых треугольников и четко очерченный полосатый узор на левой стороне; однако структура в целом не имеет видимого рисунка. Количество черных ячеек при поколении дается последовательностью
- 1, 3, 3, 6, 4, 9, 5, 12, 7, 12, 11, 14, 12, 19, 13, 22, 15, 19, ... (последовательность A070952 в OEIS )
и примерно .
Хаос
Вольфрам основал свою классификацию Правила 30 как хаотического, основываясь в первую очередь на его внешнем виде [ необходима цитата ], и позже было показано, что оно соответствует более строгим определениям хаоса, предложенным Девани и Кнудсоном. В частности, согласно критериям Девани, Правило 30 демонстрирует чувствительную зависимость от начальных условий (две начальные конфигурации, которые отличаются лишь небольшим количеством ячеек, быстро расходятся), его периодические конфигурации плотны в пространстве всех конфигураций, согласно топологии Кантора. в пространстве конфигураций (существует периодическая конфигурация с любым конечным шаблоном ячеек), и это смешивание (для любых двух конечных шаблонов ячеек существует конфигурация, содержащая один шаблон, который в конечном итоге приводит к конфигурации, содержащей другой шаблон) . Согласно критериям Кнудсона, он демонстрирует чувствительную зависимость и имеет плотную орбиту (начальная конфигурация, которая в конечном итоге отображает любой конечный образец ячеек). Обе эти характеристики хаотического поведения правила вытекают из более простого и легко проверяемого свойства правила 30: оно является перестановочным слева , что означает, что если две конфигурации C и D различаются в состоянии отдельной ячейки в позиции i , то после на один шаг новые конфигурации будут отличаться в ячейке i + 1 . [6]
Приложения
Генерация случайных чисел
Как видно из изображения выше, Правило 30 создает кажущуюся случайность, несмотря на отсутствие чего-либо, что можно было бы разумно считать случайным вводом. Стивен Вольфрам предложил использовать центральный столбец в качестве генератора псевдослучайных чисел (ГПСЧ); он проходит множество стандартных тестов на случайность, и Wolfram ранее использовал это правило в продукте Mathematica для создания случайных целых чисел. [7]
Сиппер и Томассини показали, что в качестве генератора случайных чисел Правило 30 демонстрирует плохое поведение на тесте хи-квадрат при применении ко всем столбцам правила по сравнению с другими генераторами на основе клеточных автоматов. [8] Авторы также выразили озабоченность тем, что «Относительно низкие результаты, полученные с помощью правила 30 CA, могут быть связаны с тем, что мы рассмотрели N случайных последовательностей, генерируемых параллельно, а не одну, рассмотренную Вольфрамом». [9]
Украшение
Железнодорожная станция Cambridge North украшена архитектурные панели отображения эволюции Правила 30 (или , что эквивалентно под черно-белым разворотом, Правило 135). [10] Дизайн был описан его архитектором как вдохновленный «Игрой жизни» Конвея , другим клеточным автоматом, изученным кембриджским математиком Джоном Хортоном Конвеем , но фактически не основанным на «Жизни». [11] [12]
Смотрите также
Рекомендации
- ^ Стивен Кумбс (февраль 2009). «Геометрия и пигментация ракушек» (PDF) . www.maths.nottingham.ac.uk . Ноттингемский университет . Проверено 10 апреля 2013 .
- ^ Вольфрам, С. (1983). «Статистическая механика клеточных автоматов». Ред. Мод. Phys . 55 (3): 601–644. Bibcode : 1983RvMP ... 55..601W . DOI : 10.1103 / RevModPhys.55.601 .
- ^ «Генерация случайных чисел» . Документация по Wolfram Mathematica 8 . Источник +31 декабря +2011 .
- ^ Вольфрам, С. (1985). «Криптография с клеточными автоматами». Труды достижений в криптологии - CRYPTO '85 . Конспект лекций по информатике 218, Springer-Verlag. п. 429. DOI : 10.1007 / 3-540-39799-X_32 .
- ^ Мейер, Вилли; Стаффельбах, Отмар (1991). «Анализ псевдослучайных последовательностей, порождаемых клеточными автоматами». Успехи криптологии: Учеб. Семинар по теории и применению криптографических методов, EUROCRYPT '91 . Конспект лекций по информатике 547, Springer-Verlag. п. 186. DOI : 10.1007 / 3-540-46416-6_17 .
- ^ Каттанео, Джанпьеро; Финелли, Микеле; Маргара, Лучано (2000). «Исследование топологического хаоса с помощью динамики элементарных клеточных автоматов». Теоретическая информатика . 244 (1-2): 219–241. DOI : 10.1016 / S0304-3975 (98) 00345-4 . Руководство по ремонту 1774395 .
- ^ Лекс Фридман (02.03.2018), MIT AGI: Computational Universe (Стивен Вольфрам) , получено 07.03.2018
- ^ Сиппер, Моше; Томассини, Марко (1996). «Генерация параллельных генераторов случайных чисел клеточным программированием». Международный журнал современной физики С . 7 (2): 181–190. Bibcode : 1996IJMPC ... 7..181S . DOI : 10.1142 / S012918319600017X .
- ^ Стр. 6 из Сиппер, Моше; Томассини, Марко (1996). «Генерация параллельных генераторов случайных чисел клеточным программированием». Международный журнал современной физики С . 7 (2): 181–190. Bibcode : 1996IJMPC ... 7..181S . DOI : 10.1142 / S012918319600017X .
- ^ Вольфрам, Стивен (1 июня 2017 г.), «О, черт возьми, это касается правила 30-х!» , Блог Стивена Вольфрама
- ^ Лоусон-Перфект, Кристиан (23 мая 2017 г.), «Правильный ответ по неправильной причине: клеточный автомат на новой станции Кембридж-Норт» , The Aperiodical
- ^ Purtill, Коринн. «Дань уважения на вокзале Великобритании известному математику, у которого все было хорошо, кроме его математики» . Кварц . Проверено 12 июня 2017 .
- Вольфрам, Стивен, 1985, Криптография с клеточными автоматами , CRYPTO'85.
Внешние ссылки
- Вайсштейн, Эрик В. «Правило 30» . MathWorld .
- «Объявление призов по правилу 30» . Сочинения Стивена Вольфрама . 1 октября 2019.
- Правило 30 в атласе клеточных автоматов Вольфрама
- Правило 30: Генератор псевдослучайных битов Вольфрама . Рецепт 32 в Первоначальной суповой кухне Дэвида Гриффита .
- Повторение паттернов Правила 30 . Список шаблонов, которые при повторении для заполнения ячеек автомата по правилу 30 повторяются через конечное количество временных шагов. Frans Faase, 2003. Архивировано из Оригинал на 2013-08-08
- Мощение мозаики фрактал . Базовое введение в образец Правила 30 с точки зрения эксперта по программному обеспечению LOGO Оливье Шмидт-Шевалье.
- TED Talk с февраля 2010 года . Стивен Вольфрам говорит о вычислительной теории всего, в том числе о правиле 30.