Що таке клітинний автомат?
Клітинний автомат (КА) — це сітка клітин, кожна з яких перебуває в одному з невеликої кількості станів (часто лише в двох: живий/мертвий, увімкнено/вимкнено, горить/не горить). На кожному такті годинника кожна клітина застосовує те саме правило до свого сусідства й оновлює свій стан. Жодна клітина не має особливого статусу. Жодна клітина не знає про сітку загалом.
Попри цю радикальну простоту, КА можуть симулювати майже будь-яку складну систему — що спонукало Стівена Вольфрама у 2002 році висунути гіпотезу, що сам всесвіт може бути клітинним автоматом.
"Гра в життя" Конвея
Найвідоміший КА, винайдений математиком Джоном Хортоном Конвеєм у 1970 році. Сітка нескінченна. Кожна клітина або жива, або мертва. Правило залежить від того, скільки з восьми сусідів живі:
| Поточний стан | Живих сусідів | Наступний стан |
|---|---|---|
| Мертва | Рівно 3 | Народжується (жива) |
| Жива | 2 або 3 | Виживає |
| Жива | < 2 | Помирає (недонаселеність) |
| Жива | > 3 | Помирає (перенаселеність) |
З цих чотирьох правил виникають візерунки, що можуть рухатися (глайдери), коливатися (блінкери), створювати інші візерунки (гармати), і навіть утворити повністю робочу машину Тюрінга — візерунок, здатний симулювати будь-яку комп'ютерну програму. "Гра в життя" тюрінг-повна.
Спробуйте самі: у нашому симуляторі клітинних автоматів оберіть "Гру в життя" та намалюйте випадкову ділянку. Натисніть крок один раз, двічі, п'ять разів — подивіться, як різні початкові форми мають зовсім різні долі.
Елементарні автомати Вольфрама
Стівен Вольфрам вивчав найпростіші можливі КА: одновимірні (один рядок клітин), два стани, сусідство з 3 клітин. Існує рівно 256 можливих правил (пронумерованих 0–255 у двійковій системі). Вольфрам класифікував усі їх на чотири класи:
КА в реальному світі
Ріст кристалів
Сніжинки ростуть як 2D КА на гексагональній решітці. Водяна пара осідає на наявний лід — але лише на клітинах з правильною кількістю сусідів. Результат: галузиста шестикратна симетрія. У нашій симуляції росту кристалів можна змінювати температуру й спостерігати, як з'являється й загострюється дендритне галуження.
Модель лісової пожежі
Три стани: порожньо, дерево, горить. Кожна палаюча клітина підпалює сусідів. На кожному такті дерева випадково відростають. Іскри вдаряють випадково. Система самоорганізується до критичної густини — завжди на межі катастрофічної пожежі. Цей візерунок, самоорганізована критичність, був відкритий при вивченні реальних даних про пожежі в Каліфорнії.
Реакція-дифузія (Грей-Скотт)
Два хімічні види реагують і дифундують по сітці. Різні співвідношення параметрів породжують плями (шкіра леопарда), смуги (зебра), спіралі (корали) та лабіринтоподібні візерунки — типи структур, поширені по всій біології. Природа використовує реакцію-дифузію як годинник розвитку для розміщення волосяних фолікулів, гребенів відбитків пальців і пігментних плям. Спробуйте симулятор реакції-дифузії та налаштуйте швидкості подачі й пригнічення.
Транспортний потік
Модель Нагеля-Шрекенберга — це 1D КА автомобілів на шосе. Кожен автомобіль пришвидшується або гальмує залежно від сусідів. Із цього виникають фантомні затори — хвилі стоп-старт руху без видимої причини.
Чому це важливо
Клітинні автомати розмивають межу між фізикою та обчисленням. Вони натякають, що багатство природного світу може не потребувати складних законів — лише простих правил, застосованих однорідно, повторюваних нескінченно. Щоразу, коли ви дивитеся на візерунок мушлі, піщану дюну чи хмару, ви дивитеся на результат роботи власного клітинного автомата природи.