Правило 30
Правило 30 — это элементарный клеточный автомат, предложенный Стивеном Вольфрамом в 1983 году. [2] Согласно схеме классификации Вольфрама , правило 30 относится к классу III и демонстрирует апериодическое хаотическое поведение.
Это правило представляет особый интерес, поскольку оно порождает сложные, на первый взгляд случайные закономерности из простых, четко определенных правил. По этой причине Вольфрам считает, что Правило 30 и клеточные автоматы в целом являются ключом к пониманию того, как простые правила создают сложные структуры и поведение в природе. Например, узор, напоминающий Правило 30, появляется на раковине широко распространенного вида конусных улиток Conus текстиль . Правило 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 |
Если левая, центральная и правая ячейки обозначены (p,q,r), то соответствующая формула для следующего состояния центральной ячейки может быть выражена как p xor (q или r) . Оно называется Правилом 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 генерирует кажущуюся случайность, несмотря на отсутствие чего-либо, что можно было бы разумно считать случайным вводом. Стивен Вольфрам предложил использовать центральный столбец в качестве генератора псевдослучайных чисел (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';
state = (state >> 1) ^ (state | state << 1);
}
}
Эта программа выдает следующий результат:
................................O............................... ...............................OOO.............................. ..............................OO..O............................. .............................OO.OOOO............................ ............................OO..O...O........................... ...........................OO.OOOO.OOO.......................... ..........................OO..O....O..O......................... .........................OO.OOOO..OOOOOO........................ ........................OO..O...OOO.....O....................... .......................OO.OOOO.OO..O...OOO...................... ......................OO..O....O.OOOO.OO..O..................... .....................OO.OOOO..OO.O....O.OOOO.................... ....................OO..O...OOO..OO..OO.O...O................... ...................OO.OOOO.OO..OOO.OOO..OO.OOO.................. ..................OO..O....O.OOO...O..OOO..O..O................. .................OO.OOOO..OO.O..O.OOOOO..OOOOOOO................ ................OO..O...OOO..OOOO.O....OOO......O............... ...............OO.OOOO.OO..OOO....OO..OO..O....OOO.............. ..............OO..O....O.OOO..O..OO.OOO.OOOO..OO..O............. .............OO.OOOO..OO.O..OOOOOO..O...O...OOO.OOOO............ ............OO..O...OOO..OOOO.....OOOO.OOO.OO...O...O........... ...........OO.OOOO.OO..OOO...O...OO....O...O.O.OOO.OOO.......... ..........OO..O....O.OOO..O.OOO.OO.O..OOO.OO.O.O...O..O......... .........OO.OOOO..OO.O..OOO.O...O..OOOO...O..O.OO.OOOOOO........ ........OO..O...OOO..OOOO...OO.OOOOO...O.OOOOO.O..O.....O....... .......OO.OOOO.OO..OOO...O.OO..O....O.OO.O.....OOOOO...OOO...... ......OO..O....O.OOO..O.OO.O.OOOO..OO.O..OO...OO....O.OO..O..... .....OO.OOOO..OO.O..OOO.O..O.O...OOO..OOOO.O.OO.O..OO.O.OOOO.... ....OO..O...OOO..OOOO...OOOO.OO.OO..OOO....O.O..OOOO..O.O...O... ...OO.OOOO.OO..OOO...O.OO....O..O.OOO..O..OO.OOOO...OOO.OO.OOO.. ..OO..O....O.OOO..O.OO.O.O..OOOOO.O..OOOOOO..O...O.OO...O..O..O. .OO.OOOO..OO.O..OOO.O..O.OOOO.....OOOO.....OOOO.OO.O.O.OOOOOOOOO
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Стивен Кумбс (февраль 2009 г.). «Геометрия и пигментация морских ракушек» (PDF) . www.maths.nottingham.ac.uk . Университет Ноттингема . Проверено 10 апреля 2013 г.
- ^ Вольфрам, С. (1983). «Статистическая механика клеточных автоматов». Преподобный Мод. Физ . 55 (3): 601–644. Бибкод : 1983РвМП...55..601Вт . дои : 10.1103/RevModPhys.55.601 .
- ^ «Генерация случайных чисел» . Документация Wolfram Mathematica 8 . Проверено 31 декабря 2011 г.
- ^ Вольфрам, С. (1985). «Криптография с клеточными автоматами». Труды по достижениям в криптологии - CRYPTO '85 . Конспекты лекций по информатике 218, Springer-Verlag. п. 429. дои : 10.1007/3-540-39799-X_32 .
- ^ Мейер, Вилли; Стаффельбах, Отмар (1991). «Анализ псевдослучайных последовательностей, генерируемых клеточными автоматами». Достижения криптологии – Учеб. Семинар по теории и применению криптографических методов, EUROCRYPT '91 . Конспекты лекций по информатике 547, Springer-Verlag. п. 186. дои : 10.1007/3-540-46416-6_17 .
- ^ Каттанео, Джанпьеро; Финелли, Микеле; Маргара, Лучано (2000). «Исследование топологического хаоса с помощью динамики элементарных клеточных автоматов». Теоретическая информатика . 244 (1–2): 219–241. дои : 10.1016/S0304-3975(98)00345-4 . МР 1774395 .
- ^ Лекс Фридман (2 марта 2018 г.), MIT AGI: Computational Universe (Стивен Вольфрам) , заархивировано из оригинала 19 декабря 2021 г. , получено 7 марта 2018 г.
- ^ Сиппер, Моше; Томассини, Марко (1996). «Генерация параллельных генераторов случайных чисел с помощью клеточного программирования». Международный журнал современной физики C . 7 (2): 181–190. Бибкод : 1996IJMPC...7..181S . дои : 10.1142/S012918319600017X .
- ^ Страница 6 из Сиппер, Моше; Томассини, Марко (1996). «Генерация параллельных генераторов случайных чисел с помощью клеточного программирования». Международный журнал современной физики C . 7 (2): 181–190. Бибкод : 1996IJMPC...7..181S . дои : 10.1142/S012918319600017X .
- ^ Вольфрам, Стивен (1 июня 2017 г.), «О боже, это предусмотрено правилом 30!» , блог Стивена Вольфрама
- ^ Лоусон-Перфект, Кристиан (23 мая 2017 г.), «Правильный ответ по неправильной причине: клеточный автомат на новой станции Кембридж-Север» , The A periodical
- ^ Пуртилл, Коринн. «В честь известного математика на вокзале Великобритании все было правильно, кроме его математики» . Кварц . Проверено 12 июня 2017 г.
- Вольфрам, Стивен, 1985, Криптография с помощью клеточных автоматов , CRYPTO'85.
Внешние ссылки
[ редактировать ]
- Вайсштейн, Эрик В. «Правило 30» . Математический мир .
- «Объявление призов по Правилу 30» . Сочинения Стивена Вольфрама . 1 октября 2019 г.
- Правило 30 в атласе клеточных автоматов Вольфрама.
- Правило 30: Генератор псевдослучайных битов Вольфрама . Рецепт 32 в Дэвида Гриффита . «Первобытной суповой кухне»
- Повторение моделей по Правилу 30 . Список шаблонов, которые при повторении для заполнения ячеек автомата по Правилу 30 повторяются через конечное число временных шагов. Франс Фаасе, 2003. Архивировано из оригинала 8 августа 2013 г.
- Мощение мозаики фрактал . Базовое введение в шаблон Правила 30 с точки зрения эксперта по программному обеспечению LOGO Оливье Шмидта-Шевалье.
- Выступление TED от февраля 2010 года . Стивен Вольфрам говорит о компьютерной теории всего, среди прочего, о правиле 30.