Простейшие клеточные автоматы и их практическое применение

Этот мир просто охренеть какой сложный, каждый день поражаюсь.

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

И знаете, что удивительно? Этот подход замечательно работает. Ну, почти всегда. По крайней мере, ничего лучше мы до сих пор не придумали.

Но вообще-то я не об этом. Я хочу рассказать об одной чрезвычайно интересной как с эстетической, так и с математической точки зрения категории этих самых моделей.

Да, я о клеточных автоматах, а именно — об их подмножестве, простейших клеточных автоматах (Elementary cellular automaton). В этой статье я поведаю, что это такое, какие они бывают, какими свойствами обладают, а также отвечу на главный, на мой взгляд, и совершенно правильный вопрос, который часто несправедливо игнорируется в подобных статьях. Звучит он так: А это всё вообще зачем?

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

Я искренне надеюсь, что после прочтения статьи вы сами захотите поиграться с ними, и на этот случай у меня припасен собранный из JS и палок генератор.

Унылая теория

Что такое клеточный автомат?

Дискретная модель, представляющая собой сетку произвольной размерности, каждая клетка которой в каждый момент времени может принимать одно из конечного множества состояний, и определено правило перехода клеток из одного состояния в другое.
Примеры: «Жизнь» Конуэя, Автомат Фон Неймана, Wireworld, Модель сегрегации Шеллинга.

Какие они бывают?

В зависимости от размерности решетки:
одно-, дву-, трёхмерные, и т.д.
Например, Правило 110 и другие, освещенные в этой статье, — одномерные, «Жизнь» — двумерная.

В зависимости от количества возможных состояний:
бинарные, троичные, и т.д.

В разных клеточных автоматах может по-разному определяться окрестность клетки, то есть, множество клеток, от которых будет зависеть состояние в следующий момент времени. Это может быть, например, окрестность Фон Неймана различных рангов или окрестность Мура.

КА бывают синхронные и асинхронные. В синхронных все клетки системы обновляются одновременно, в асинхронных — каждая делает это независимо.

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

А что же тогда такое простейший клеточный автомат?

Одномерный бинарный (с двумя возможными состояниями) клеточный автомат, где состояние клетки в каждый момент времени зависит только от её собственного состояния и состояний смежных с ней клеток в предыдущий момент времени.

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

Для начала определимся с терминологией. Так как вариантов таких автоматов всего 256, тот самый Вольфрам (я часто буду на него ссылаться) не стал сильно заморачиваться и предложил называть их числами от 0 до 255. Это именование по причине своей лаконичности и удобства отлично прижилось, и с тех пор оно называется, вы не поверите, "Код Вольфрама".

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

Что означают коды Вольфрама

Рассмотрим сразу на примере.
Возьмём номер правила, например, 110.
1. 110₁₀ = 01101110₂.
2. Впишем цифры двоичного представления числа в таблицу:

111	110	101	100	011	010	001	000
0	1	1	0	1	1	1	0

В зависимости от состояний соседа слева, самой клетки и соседа справа (первая строка таблицы) на следующем шаге клетка примет одно из состояний, указанных во второй строке.

Еще более наглядно это можно представить так:

Также Вольфрам предложил разделить клеточные автоматы на четыре класса по типу поведения:

1 класс: все клетки быстро принимают одинаковое состояние, которое становится стабильным.
Например, Правило 40:

2 класс: состояние всех клеток быстро стабилизируется, либо возникают периодические колебания.
Например, Правила 3 и 33:

3 класс: автомат порождает хаотические, непериодические структуры. Небольшие изменения исходного состояния влекут значительные изменения в результате.
Например, правило 22:

4 класс: автомат порождает сложные, взаимодействующие между собой структуры, способные выживать длительное время, однако не достигает стабильности.
Например, правило 193:

ПКА в жизни

Правило 30

Иногда элементарные клеточные автоматы обнаруживаются в совершенно неожиданных местах.
Вот, например, посмотрите, какой милашка.

Только не обольщайтесь. Он вас не любит. Это — Текстильный конус, самый опасный для человека моллюск из семейства Конусы. Противоядия от его яда пока нет.

Рисунок на его раковине — не что иное как узор, порожденный «Правилом 30». По крайней мере, именно так считают в Ноттингемском университете.

Так выглядит развитие «Правила 30» из одной точки.

То же самое Правило 30 до недавнего времени использовалось в пакете Mathematica для генерации псевдослучайных чисел. Это стало возможным благодаря важному его свойству: порождаемые им результаты хаотичны, то есть, незначительное изменение в начальных условиях оказывает значительное влияние на порождаемые результаты.

Однако, существует огромное множество начальных условий, при которых правило порождает повторяющиеся паттерны. Например, если в начальных условиях «жива» каждая 14-я клетка, в результате получается вот такой скандинавский свитер.

Правило 110

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

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

Тут также видны и периодические (что интересно, с разными периодами), и хаотические.
Не буду долго тянуть, в 2000 году Мэтью Кук доказал, что этот клеточный автомат является Тьюринг-полным, то есть, на его основе можно реализовать любую вычислимую функцию.

Фракталы

Есть целый ряд клеточных автоматов (правила 18, 22, 126, 161, 182, 218, etc.), которые, развиваясь из одной точки, порождают фрактальные изображения. Например, рисунок правила 22 — это треугольник Паскаля по модулю 2 (эдакий дискретный аналог «Салфетки Серпинского»). Связь салфетки Серпинского и треугольника Паскаля уже достойно освещалась на Хабре три года назад.
А выглядит всё это счастье так:

Правило 161 порождает инвертированный вариант того же самого фрактала.

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

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

Иначе вместо вполне ожидаемого полностью закрашенного прямоугольника (эволюция правила 161 с начальным состоянием, полностью состоящим из живых клеток) можно увидеть кое-то неожиданное:

Правило 184

Правило 184 обладает несколькими интересными особенностями, благодаря которым оно широко применяется в математическом моделировании:

• После каждого шага количество «живых» клеток остается неизменным
• Правило в зависимости от исходного состояния может вести себя как правило класса 2 или 4.
• Чем меньше «живых» клеток в исходном состоянии, тем быстрее автомат стабилизируется

С его помощью довольно эффективно моделируются транспортные потоки.

Каждый отдельно взятый автомобиль передвигается вперед, в то время как волна траффика движется назад.
(картинка с Википедии)

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

Заключение

Математика, как ни крути, царица наук (хотя вряд ли её саму можно считать наукой), и работы в ней — непочатый край. Существует множество нерешенных физических задач, многие из которых не решены только из-за того, что еще не придуман математический аппарат для их решения.
А бывает и наоборот — есть, казалось бы, никому не нужный математический аппарат, и тут возникает задача, для которой он внезапно оказывается пригодным (как, например, с правилом 184 и транспортными потоками).
Да и, в конце-то концов, красиво же.

Ссылки по теме:

Атлас простейших клеточных автоматов от Стивена Вольфрама;
Книга Вольфрама New Kind of Science;
Генератор простейших клеточных автоматов за авторством вашего непокорного слуги (исходники);
Еще один замечательный генератор от товарища по имени Nico Disseldorp.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.