Правило 30

Элементарный клеточный автомат

Текстильная оболочка Conus, внешне похожая на Правило 30. ^[1]

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

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

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

Набор правил

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

Если левая, центральная и правая ячейки обозначены (p,q,r) , то соответствующая формула для следующего состояния центральной ячейки может быть выражена как p xor (q или r) . Оно называется Правилом 30, потому что в двоичном формате 00011110 2 ₌ 30.

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

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

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

Правило 30 клеточный автомат

Здесь вертикальная ось представляет время, а любое горизонтальное сечение изображения представляет состояние всех ячеек массива в определенный момент эволюции шаблона. В этой структуре присутствует несколько мотивов, таких как частое появление белых треугольников и четко выраженный полосатый узор на левой стороне; однако структура в целом не имеет заметной закономерности. Количество черных клеток при генерации определяется последовательностью ${\displaystyle n}$

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

и составляет примерно . ^{[ нужна цитата ]} ${\displaystyle n}$

Хаос

Правило 30 соответствует строгим определениям хаоса, предложенным Девани и Кнудсоном. В частности, правило 30, согласно критериям Девани, проявляет чувствительную зависимость от начальных условий (две начальные конфигурации, отличающиеся лишь небольшим числом ячеек, быстро расходятся), его периодические конфигурации плотны в пространстве всех конфигураций, согласно топологии Кантора. на пространстве конфигураций (существует периодическая конфигурация с любым конечным набором ячеек), а также перемешивание ( для любых двух конечных наборов ячеек существует конфигурация, содержащая один узор, которая в конечном итоге приводит к конфигурации, содержащей другой узор) . Согласно критериям Кнудсона, он демонстрирует чувствительную зависимость и имеет плотную орбиту (начальная конфигурация, которая в конечном итоге отображает любой конечный набор ячеек). Обе эти характеристики хаотического поведения правила следуют из более простого и легко проверяемого свойства Правила 30: оно является левым перестановочным , что означает, что если две конфигурации C и D различаются состоянием одной ячейки в позиции i , то после за один шаг новые конфигурации будут отличаться в ячейке i + 1 . ^[6]

Приложения

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

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

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

Украшение

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

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

Программирование

Обновление состояния может быть выполнено быстро с помощью побитовых операций , если значения ячеек представлены битами в пределах одного (или нескольких) компьютерных слов. Здесь показано на C++ :

#include <stdint.h> #include <iostream>  int main () { uint64_t state = 1u << 31 ; for ( int i = 0 ; i < 32 ; ++ i ) { for ( int j = 64 ; j -- ;) { std :: cout << char ( state >> j & 1 ? 'O' : '. ' ); } std :: cout << '\n' ; состояние = ( состояние >> 1 ) ^ ( состояние | состояние << 1 ); } }                                                    

Эта программа выдает следующий результат:

.................О................. .................................ООО............ .............................ОО..О........... ..........................ОООООО........... ......................................ОО..О...О............... .................................ОООООООО.................. ...................ОО..О....О..О........... .................................ОООООООООО............... .............................ОО..О...ООО.....О........... .......................ОООООООООООООООО ..................ОО..О....О.ОООО.ОО..О........... ......................ОООООООООООООООООООООООООООООООООООООООООООООООООООО ..........................ОО..О...ООО..ОО..ОО.О...О.......... ......................ООООООООООООООООООО .......ОО..О....О.ООО...О..ООО..О..О........ .............ОООООООООООООООООООООООООООООООООООООООООООООООООООООО................ОО..О...ООО..ОООО.О....ООО......О....... ..........ОООО.ОО..ООО....ОО..ОО..О....ООО........... .................ОО..О....О.ООО..О..ОО.ООО.ОООО..ОО..О....... .................ОО.ООО..ОО.О..ООООО..О...О...ООО.ОООО........................ОО..О...ООО..ОООО.....ООО.ООО.ОО...О...О....... .............ОООООООООООООООООООООООО..........ОО..О....О.ООО..О.ООО.ОО.О..ООО.ОО.ОО..О..О....... ...........ОООООООООООООООООООООООООООООООООООООООООООООООООООООООООООООООООООООООООООООООоо........ОО..О...ООО..ОООО...ОООООО...О.ООООО.О..О.....О..............ООООООООООООООООООООООООООООООООООООООООООООООООООООООООООООООООООООООООООООООООООоо......ОО..О....О.ООО..О.ОО.О.ОООО..ОО.ООО...ОО...О.ОО..О.. ........ОООООООООООООООООООООООООООООООООО.......ОО..О...ООО..ОООО...ООО.ОО.ООООООООООООООО...... oo.oooo.oo..ooo ... o.oo .....ОО..О....О.ООО..О.ОО.ОООООО.О..ООООО..О...О.ОО...О..О..О..ОО.ООО..ОО.О..ООО.О..О.ОООО.....ОООО.....ОООО.ОООООООООО

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

• Правило 90
• Правило 110
• Правило 184

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

1. Стивен Кумбс (февраль 2009 г.). «Геометрия и пигментация морских ракушек» (PDF) . www.maths.nottingham.ac.uk . Университет Ноттингема . Проверено 10 апреля 2013 г.
2. Вольфрам, С. (1983). «Статистическая механика клеточных автоматов». Преподобный Мод. Физ . 55 (3): 601–644. Бибкод : 1983RvMP...55..601W. doi : 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. Лекс Фридман (02 марта 2018 г.), MIT AGI: Computational Universe (Стивен Вольфрам), заархивировано из оригинала 19 декабря 2021 г. , получено 7 марта 2018 г.
8. Сиппер, Моше; Томассини, Марко (1996). «Генерация параллельных генераторов случайных чисел с помощью клеточного программирования». Международный журнал современной физики C . 7 (2): 181–190. Бибкод : 1996IJMPC...7..181S. дои : 10.1142/S012918319600017X.
9. Страница 6 Сиппер, Моше; Томассини, Марко (1996). «Генерация параллельных генераторов случайных чисел с помощью клеточного программирования». Международный журнал современной физики C . 7 (2): 181–190. Бибкод : 1996IJMPC...7..181S. дои : 10.1142/S012918319600017X.
10. Вольфрам, Стивен (1 июня 2017 г.), «О боже, это описано в Правиле 30!», Блог Стивена Вольфрама
11. Лоусон-Перфект, Кристиан (23 мая 2017 г.), «Правильный ответ по неправильной причине: клеточный автомат на новой станции Кембридж-Север», The A periodical
12. Пуртилл, Коринн. «В честь знаменитого математика на вокзале Великобритании все было правильно, кроме его математики». Кварц . Проверено 12 июня 2017 г.

• Вольфрам, Стивен, 1985, Криптография с помощью клеточных автоматов , CRYPTO'85.

Внешние ссылки

• Вайсштейн, Эрик В. «Правило 30». Математический мир .
• «Объявление призов по Правилу 30». Сочинения Стивена Вольфрама . 1 октября 2019 г.
• Правило 30 в атласе клеточных автоматов Вольфрама.
• Правило 30: Генератор псевдослучайных битов Вольфрама. Рецепт 32 в «Первобытной суповой кухне» Дэвида Гриффита.
• Повторение моделей Правила 30. Список шаблонов, которые при повторении для заполнения ячеек автомата по Правилу 30 повторяются через конечное число временных шагов. Франс Фаасе, 2003. Архивировано из оригинала 8 августа 2013 г.
• Мощение мозаики фрактал. Базовое введение в шаблон Правила 30 с точки зрения эксперта по программному обеспечению LOGO Оливье Шмидта-Шевалье.
• Выступление на TED, февраль 2010 года. Стивен Вольфрам рассказывает о компьютерной теории всего, среди прочего, о правиле 30.