Правило 30 - Википедия - Rule 30

Эта статья о клеточном автомате. Правила федерального суда США см. Федеральные правила гражданского судопроизводства и осаждение (закон).
А Конус текстиль оболочка похожа на Правило 30.[1]

Правило 30 является элементарный клеточный автомат представлен Стивен Вольфрам в 1983 г.[2] С помощью Схема классификации Вольфрама, Правило 30 - это правило класса III, показывающее апериодические, хаотичный поведение.

Это правило представляет особый интерес, поскольку оно создает сложные, на первый взгляд случайные шаблоны из простых, четко определенных правил. Из-за этого Вольфрам считает, что Правило 30 и клеточные автоматы в целом являются ключом к пониманию того, как простые правила создают сложные структуры и поведение в природе. Например, узор, напоминающий Правило 30, появляется на раковине широко распространенных видов конусообразных улиток. Конус текстиль. Правило 30 также использовалось как генератор случайных чисел в Mathematica,[3] и также был предложен как возможный потоковый шифр для использования в криптография.[4][5]

Правило 30 названо так потому, что 30 - наименьшее Код Wolfram который описывает его набор правил (как описано ниже). Зеркальное отображение, дополнение и зеркальное дополнение правила 30 имеют коды Вольфрама 86, 135 и 149 соответственно.

Набор правил

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

текущий образец111110101100011010001000
новое состояние для центральной ячейки00011110

Соответствующая формула: [left_cell XOR (central_cell OR right_cell)]. Это называется Правило 30, потому что в двоичный, 000111102 = 30.

На следующей диаграмме показан созданный узор с ячейками, окрашенными в соответствии с предыдущим состоянием их соседства. Более темные цвета представляют собой «1», а более светлые цвета представляют «0». Время увеличивается вниз по вертикальной оси.

Клеточные автоматы, работающие под управлением Wolfram-rule-30.svg

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

Следующий шаблон возникает из начального состояния, в котором одна ячейка с состоянием 1 (показанная черным) окружена ячейками с состоянием 0 (белая).

Rule30-256-rows.png
Правило 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 отличаются состоянием отдельной ячейки в позиции я, то после одного шага новые конфигурации будут отличаться в ячейке я + 1.[6]

Приложения

Генерация случайных чисел

Как видно из изображения выше, Правило 30 создает кажущуюся случайность, несмотря на отсутствие чего-либо, что можно было бы разумно считать случайным вводом. Стивен Вольфрам предложил использовать центральную колонну в качестве генератор псевдослучайных чисел (ГПСЧ); он проходит множество стандартных тестов на случайность, и Wolfram ранее использовал это правило в продукте Mathematica для создания случайных целых чисел.[7]

Сиппер и Томассини показали, что Правило 30 как генератор случайных чисел демонстрирует плохое поведение на критерий хи-квадрат при применении ко всем столбцам правил по сравнению с другими генераторами на основе клеточных автоматов.[8] Авторы также выразили обеспокоенность тем, что «Относительно низкие результаты, полученные с помощью правила 30 CA, могут быть связаны с тем, что мы рассматривали N случайных последовательностей, генерируемых параллельно, а не одну, рассмотренную Wolfram».[9]

Украшение

Деталь облицовки северного железнодорожного вокзала Кембриджа

В Кембриджский Северный вокзал украшен архитектурными панелями, отображающими эволюцию Правила 30 (или, что эквивалентно, с черным и белым переворотом, Правило 135).[10] Его архитектор описал дизайн как вдохновленный Игра жизни Конвея, другой клеточный автомат, изученный кембриджским математиком Джон Хортон Конвей, но на самом деле не основан на Жизни.[11][12]

Смотрите также

Рекомендации

  1. ^ Стивен Кумбс (февраль 2009 г.). «Геометрия и пигментация ракушек» (PDF). www.maths.nottingham.ac.uk. Ноттингемский университет. Получено 2013-04-10.
  2. ^ Вольфрам, С. (1983). «Статистическая механика клеточных автоматов». Ред. Мод. Phys. 55 (3): 601–644. Bibcode:1983РвМП ... 55..601Вт. Дои:10.1103 / RevModPhys.55.601.
  3. ^ «Генерация случайных чисел». Документация по Wolfram Mathematica 8. Получено 31 декабря 2011.
  4. ^ Вольфрам, С. (1985). «Криптография с клеточными автоматами». Труды достижений в криптологии - CRYPTO '85. Конспект лекций по информатике 218, Springer-Verlag. п. 429. Дои:10.1007 / 3-540-39799-X_32.
  5. ^ Мейер, Вилли; Стаффельбах, Отмар (1991). «Анализ псевдослучайных последовательностей, порождаемых клеточными автоматами». Успехи криптологии: Учеб. Семинар по теории и применению криптографических методов, EUROCRYPT '91. Конспект лекций по информатике 547, Springer-Verlag. п. 186. Дои:10.1007/3-540-46416-6_17.
  6. ^ Каттанео, Джанпьеро; Финелли, Микеле; Маргара, Лучано (2000). «Исследование топологического хаоса с помощью динамики элементарных клеточных автоматов». Теоретическая информатика. 244 (1–2): 219–241. Дои:10.1016 / S0304-3975 (98) 00345-4. МИСТЕР  1774395.
  7. ^ Лекс Фридман (2018-03-02), MIT AGI: Computational Universe (Стивен Вольфрам), получено 2018-03-07
  8. ^ Сиппер, Моше; Томассини, Марко (1996). «Генерация параллельных генераторов случайных чисел клеточным программированием». Международный журнал современной физики C. 7 (2): 181–190. Bibcode:1996IJMPC ... 7..181S. Дои:10.1142 / S012918319600017X.
  9. ^ Страница 6 из Сиппер, Моше; Томассини, Марко (1996). «Генерация параллельных генераторов случайных чисел клеточным программированием». Международный журнал современной физики C. 7 (2): 181–190. Bibcode:1996IJMPC ... 7..181S. Дои:10.1142 / S012918319600017X.
  10. ^ Вольфрам, Стивен (1 июня 2017 г.), «О, боже мой, это касается правила 30-х!», Блог Стивена Вольфрама
  11. ^ Лоусон-Перфект, Кристиан (23 мая 2017 г.), «Правильный ответ по неправильной причине: сотовый автомат на новой станции Cambridge North», Апериодическое издание
  12. ^ Purtill, Коринн. «Дань уважения на вокзале Великобритании к известному математику, который понял все правильно, кроме его математики». Кварцевый. Получено 2017-06-12.

внешняя ссылка