Найпростіші клітинні автомати та їх практичне застосування

Цей світ просто охренеть який складний, кожен день дивуюся.

Щоб хоч якось його пізнавати і при цьому не з'їхати з глузду, нам, людям, з нашими жалюгідними мізками доводиться задумливо дивитися на події, аналізувати побачене і будувати моделі — абстракції, за допомогою яких ми з деякою точністю дещо іноді можемо передбачати і навіть наївно вважати, що розуміємо, що ж насправді відбувається.

І знаєте, що дивно? Цей підхід чудово працює. Ну, майже завжди. Принаймні, нічого краще ми до цих пір не придумали.

Але взагалі-то я не про це. Я хочу розповісти про одну надзвичайно цікавою як з естетичної, так і з математичної точки зору категорії цих самих моделей.

image

Так, я про клітинних автоматах, а саме — про їх підмножині, найпростіших клітинних автоматах (Elementary cellular автомат). У цій статті я розповім, що це таке, які вони бувають, якими властивостями володіють, а також відповім на головний, на мій погляд, і абсолютно правильне питання, яке часто несправедливо ігнорують у подібних статтях. Звучить він так: А це все взагалі навіщо?

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

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


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

Які вони бувають?В залежності від розмірності решітки:
одно-, дво-, тривимірні, і т. д.
Наприклад, Правило 110 та інші, висвітлені у цій статті, — одномірні, «Життя» — двовимірна.

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

У різних клітинних автоматах може по-різному визначатися околиця клітини, тобто, безліч клітин, від яких буде залежати стан в наступний момент часу. Це може бути, наприклад, околиця Фон Неймана різних рангів або околиця Мура.

КА бувають синхронні і асинхронні. У синхронних всі клітини системи оновлюються одночасно, в асинхронних — кожна робить це незалежно.

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

А що ж тоді таке найпростіший клітинний автомат?Одновимірний бінарний (з двома можливими станами) клітинний автомат, де стан клітини в кожен момент часу залежить тільки від її власного стану і станів суміжних з нею клітин в попередній момент часу.

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

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

Я вас розумію, мені теж ліньки ходити по посиланнях, тому я коротко розповім про те, як ці коди розуміти. А якщо ви це і без мене чудово знаєте, можете не розгортати спойлер, а просто читати далі.

Що означають коди ВольфрамуРозглянемо відразу на прикладі.
Візьмемо номер правила, наприклад, 110.
1. 11010 = 011011102.
2. Впишемо цифри двійкового представлення числа в таблицю:
111 110 101 100 011 010 001 000
0 1 1 0 1 1 1 0


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

Ще більш наочно це можна представити так:
правило 110


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

1 клас: всі клітини швидко приймають однакову стан, який стає стабільним.
Наприклад, Правило 40:
Правило 40

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

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

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

ПКА в життя

Правило 30
Іноді елементарні клітинні автомати виявляються в зовсім несподіваних місцях.
Ось, наприклад, подивіться, який милашка.



Тільки не спокушайтеся. Він вас не любить. Це — Текстильний конус, найнебезпечніший для людини молюск з сімейства Конуси. Протиотрути від його отрути поки немає.

Малюнок на його раковині — не що інше як візерунок, породжений «Правилом 30». Принаймні, саме так вважають в Нотінгемському університеті.


Так виглядає розвиток «Правила 30» з однієї точки.

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

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


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

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

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

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

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


До речі, забув згадати один важливий момент, що стосується реалізації автоматів.
Для того, щоб уникнути «крайового ефекту», тобто, меж впливу на прикордонні клітини, потрібно замкнути автомат в кільце, тобто зробити крайню ліву клітинку правим сусідом крайньої правої, і навпаки.
Інакше замість цілком очікуваного повністю зафарбованого прямокутника (еволюція правила 161 з початковим станом, повністю складається з живих клітин) можна побачити дещо несподіване:
Правило 161 ФЭЙЛ

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


З його допомогою досить ефективно моделюються транспортні потоки.
image
Кожен окремо взятий автомобіль пересувається вперед, в той час як хвиля трафіку рухається назад.
(картинка з Вікіпедії)

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

Висновок
Математика, як не крути, цариця наук (хоча навряд чи її саму можна вважати наукою), і роботи в ній — непочатий край. Існує безліч невирішених фізичних задач, багато з яких не вирішені тільки з-за того, що ще не придуманий математичний апарат для їх вирішення.
А буває і навпаки — є, здавалося б, нікому не потрібний математичний апарат, і тут виникає задача, для якої він раптово виявляється придатним (як, наприклад, з правилом 184 і транспортними потоками).
Та й, в кінці-то кінців, красиво ж.

Посилання по темі:
Атлас найпростіших клітинних автоматів від Стівена Вольфраму;
Книга Вольфраму New Kind of Science;
Генератор найпростіших клітинних автоматів за авторством вашого непокірного слуги (джерело;
Ще один чудовий генератор від товариша по імені Nico Disseldorp.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.