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

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

Игра "Жизнь" — один из множества примеров двумерных клеточных автоматов с детерминированными правилами. Я напомнил о ней для того, чтобы подготовить вас, дорогие читатели, к краткой лекции о простейших одномерных клеточных автоматах, досконально изученных Стивеном Вольфрамом.

Элементарный клеточный автомат — это одномерный автомат, клетки которого принимают только два значения: 0 (белый) и 1 (черный). Как и в "Жизни", новое состояние каждой клетки определяется ее соседями (левым и правым) и ей самой. То есть новое состояние [b] клетки [a] определяет триплет

([a-1], [a], [a+1]) ? [b].

Так как любой триплет состоит только из нулей и единиц, то он является двоичной записью трехбитного числа от 0 до 7. Всего мы можем построить 8 уникальных триплетов:

000

001

010

111

Я записал каждый триплет на отдельной строчке, а на рисунке все они вытянуты в линию.

Каждому триплету сопоставим правило, которое переводит центральную клетку в следующее состояние. Например, мы можем определить следующие правила эволюции центральной клетки (привожу часть правил, остальные нарисованы):

000 ? 0

001 ? 1

010 ? 1

111 ? 0.

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

Другими словами любому восьмибитному числу от 0 до 255 соответствует единственный элементарный клеточный автомат, правила которого полностью описывает битовое представление этого числа. То есть существует ровно 256 элементарных клеточных автомата.

Такой способ обозначения клеточных автоматов называется "Кодом Вольфрама", так как он был впервые описан Стивеном Вольфрамом в статье 1983 года.

Statistical Mechanics of Cellular Automata (1983)

https://doi.org/10.1103/RevModPhys.55.601

[?]

Эволюция ЭКА начинается с произвольной начальной конфигурации черных и белых клеток. Для наглядности, в качестве начальной конфигурации часто используют единственную черную клетку, которая генерирует черно-белый узор.

[?]

Но если начать развитие КА со случайной черно-белой полосы, то получится более красивый паттерн.

[?]

Паттерны, построенные клеточными автоматами, отличаются многообразием. Стивен Вольфрам сумел выделить в них общие закономерности, сгруппировав все ЭКА в четыре класса.

Класс 1.

Быстро сходится к состоянию из нулей или единиц.

Класс 2.

Быстро сходится к циклическому или стабильному состоянию.

[?]

Класс 3.

Генерирует случайные состояния.

Класс 4.

Образуется как области с циклическими или стабильными состояниями, так и структуры, которые взаимодействуют друг с другом сложными способами.

[?]

Рассмотрим некоторые необычные ЭКА.

Правило 30. Хаотичный КА.

В узоре, генерируемом этим клеточным автоматом, видны два мотива: частое повторение белых треугольников и выраженная полосатость в левой части узора. Однако в целом текстура не имеет выраженной закономерности.

[?]

По этой причине КА 30 использовался в Вольфрам Математике для генерации псевдослучайной последовательности чисел. Для этого из центральной колонки алгоритм выбирал n битов, что давало первое псевдослучайное число. Затем следующие n битов, описывающие следующее псевдослучайное число, и так далее. Для придания большей рандомности алгоритм пропускал несколько первых битов.

[?]

Правило 90. Аддитивный треугольник Серпинского.

Клеточный автомат с правилом 90 из единственной черной клетки строит треугольник Серпинского. А из случайной полосы черно-белых клеток создает полотно из хаотично расположенных разноразмерных треугольников.

Интересно, что каждая конфигурация, сгенерированная автоматом, имеет ровно четыре предшественника. То есть в каждое наблюдаемое состояние можно достигнуть из четырех отличающихся предыдущих состояний.

С точки зрения булевой алгебры состояние каждой новой клетки равно сумме по модулю два ее предыдущих соседей. То есть правила автомата выполняют операцию XOR.

[?]

По этой причине КА 90 назван аддитивным: на каждом шаге центральная клетка не влияет на результат, который зависит только от состояния двух соседних клеток.

Данная особенность позволяет создавать визуализацию движения узоров, сгенерированных двумя одинаковыми аддитивными клеточными автоматами. Для этого сначала построим узор КА из одной черной клетки. Затем два узора из двух рядом расположенных черных клеток. Получим два наложенных друг на друга треугольника Серпинского. Далее продолжим сдвигать вторую черную клетку на один шаг, удаляя ее от первой. В результате построенные треугольники Серпинского также будут сдвигаться, инвертируя друг друга в местах пересечения.

То есть при аддитивном правиле узоры клеточных автоматов при наложении не уничтожают друг друга, а остаются такими же, инвертируясь в местах пересечения.

Всего существует ровно семь аддитивных ЭКА:

0, 60, 90, 102, 150, 170, 204, 240.

https://mathworld.wolfram.com/AdditiveCellularAutomaton.html

[?]

Интересен также КА с правилом 184, который имитирует дорожный трафик и осаждение частиц на неровную поверхность.

И КА с правилом 110, который является универсальным, так как из него можно построить машину Тьюринга.

И КА с правилом 62, где случайные структуры взаимодействуют сложным образом, но, в конце-концов, уничтожают друг друга.

И КА с правилом 73, где комбинация 0110 сохраняется в следующих поколениях, что создает блокирующие стены, препятствующие перемещению клеток.

Но эти КА — уже другая история.

—-----

Напоследок порекомендую прекрасный генератор элементарных клеточных автоматов:

https://oshibka404.github.io/eca/

И еще один, наглядный, но менее удобный в управлении:

https://sciencevsmagic.net/eca/

Источник: sciencevsmagic.net

Комментарии: