Правила Життя
У 1970 році британський математик Джон Хортон Конвей поставив перед собою завдання: знайти найпростіший можливий набір правил для двовимірної сітки клітин, що породжував би поведінку, яка не була б ані тривіально мертвою, ані вибухово зростаючою. Після місяців пошуків він дійшов до трьох правил, які застосовуються одночасно до кожної клітини на кожному кроці часу:
- Жива клітина з 2 або 3 живими сусідами виживає до наступного покоління.
- Мертва клітина рівно з 3 живими сусідами оживає (є «народженою»).
- Усі інші живі клітини гинуть (від самотності при 0–1 сусідах або від перенаселення при 4–8 сусідах), а всі інші мертві клітини залишаються мертвими.
Це весь звід правил Гри життя Конвея. Жодних інших параметрів. Кожна клітина рахує вісім своїх найближчих сусідів (включно з діагональними) і застосовує ці правила. Усі клітини оновлюються одночасно на основі стану попереднього покоління. Сітка, околиця та три правила — це все, що потрібно.
Конвей ретельно підбирав свої правила. Правило 1 забезпечує стабільність — успішні візерунки можуть зберігатися. Правило 2 дозволяє зростання — можуть народжуватися нові клітини. Умови загибелі запобігають тривіальному неконтрольованому розростанню. Він хотів знайти найпростіші правила, що врівноважували б ці протилежності, і система, яку він знайшов, виявилась набагато багатшою, ніж будь-хто очікував.
Емерджентні структури
Найбільш вражаюча риса Життя полягає в тому, що його візерунки не були спроєктовані — вони були відкриті. Протягом перших кількох років після публікації правил (спершу в журналі Scientific American Мартіном Гарднером) ентузіасти виявили дивовижну різноманітність стабільних структур суто експериментальним шляхом:
«Натюрморти» (still lifes) — це візерунки, які ніколи не змінюються. Найпростіший — блок 2×2 з чотирьох живих клітин: кожна клітина має рівно 3 живих сусідів, тому всі виживають, а жодна з навколишніх мертвих клітин не має рівно 3 сусідів, тож ніхто не народжується. Вулик (6 клітин), буханка (7 клітин) і човен (5 клітин) — інші класичні натюрморти, кожен стабільний з власних геометричних причин.
Осцилятори циклічно проходять через повторювану послідовність станів. Блимач — ряд із трьох клітин — щопокоління змінюється з горизонтального на вертикальний (період 2). Пульсар (період 3) — більший і складніший осцилятор. Існують осцилятори з періодом 15 і навіть 30, що проходять через десятки проміжних конфігурацій, перш ніж повернутися до початкового стану.
Космічні кораблі — найбільш вражаюче відкриття: візерунки, що рухаються по сітці. Планер, знайдений Річардом Гаєм у 1970 році, складається лише з 5 клітин у формі літери L. Він циклічно проходить 4 покоління, перш ніж відтворити себе, зміщеним на одну клітину по діагоналі — він рухається по сітці зі швидкістю c/4 (одна клітина за 4 покоління, де c — максимально можлива швидкість). Легкий космічний корабель рухається горизонтально зі швидкістю c/2.
Жоден з цих об'єктів не був закладений Конвеєм. Вони виникають із самих правил. Це і є визначення емерджентності: макроскопічні структури й поведінка, що постають із мікроскопічних правил і не можуть бути зведені до них без втрати чогось суттєвого.
Універсальні обчислення
У листопаді 1970 року математик Білл Госпер відкрив гармату Госпера, що стріляє планерами (Gosper Glider Gun): візерунок із 36 клітин, який осцилює з періодом 30 і випускає новий планер кожні 30 поколінь. Це був перший знайдений у Житті візерунок із необмеженим зростанням — раніше Конвей припускав, що жоден скінченний візерунок не зможе зростати без обмеження.
Гармата планерів відкрила двері до чогось набагато глибшого. Планери можна використовувати як сигнали: потік планерів являє собою бінарну 1, проміжок — 0. Використовуючи ретельно розташовані візерунки, ці потоки планерів можна змусити взаємодіяти так, щоб реалізувати логічні операції:
- Два потоки планерів, що стикаються і взаємознищуються: логічний вентиль І (AND)
- Потік планерів, що триває, якщо його не заблоковано: вентиль НЕ (NOT)
- Комбінації цих елементів: довільна булева логіка
Оскільки будь-яке обчислення можна побудувати з булевої логіки, Життя є тюрінг-повним: воно може симулювати будь-який алгоритм, який здатний виконати будь-який комп'ютер, за умови достатнього простору й часу. Це було доведено Конвеєм і колегами невдовзі після відкриття гармати планерів.
Те, що сталося далі, вражало навіть за мірками рекреаційної математики. Ентузіасти побудували в Житті працюючі суматори, помножувачі та комірки пам'яті. У 2000 році Пол Ренделл сконструював у Житті працюючу машину Тюрінга. У 2018 році команда побудувала в Житті програмований комп'ютер — включно з дисплеєм, пам'яттю та набором інструкцій — здатний виконувати довільні програми. Уся ця конструкція вміщується в область шириною близько 1,7 мільярда клітин.
Елементарні клітинні автомати Вольфрама
У той час як Життя Конвея працює у двох вимірах, Стівен Вольфрам систематично дослідив найпростіші можливі клітинні автомати: одновимірні, двостанові (0 або 1), з правилами, що залежать від клітини та двох її найближчих сусідів. Новий стан кожної клітини залежить від 8 можливих комбінацій себе самої та двох сусідів (2³ = 8), і для кожної комбінації правило визначає 0 або 1. Це дає 2⁸ = 256 можливих правил, пронумерованих від 0 до 255.
Вольфрам візуалізував їх, укладаючи послідовні покоління вертикально одне під одним — кожен рядок відповідає одному кроку часу. Отримані візерунки розпадаються на чотири вражаючі класи:
- Клас I: сітка еволюціонує до однорідного фіксованого стану. (Приклад: Правило 0 — всі клітини гинуть.)
- Клас II: сітка еволюціонує до простого періодичного візерунка з осциляторів або нерухомих точок. (Приклад: Правило 4.)
- Клас III: сітка еволюціонує хаотично, породжуючи очевидну випадковість. Правило 30 — канонічний приклад: воно генерує візерунки, що настільки добре проходять статистичні тести на випадковість, що Вольфрам десятиліттями використовував його як генератор випадкових чисел у Mathematica.
- Клас IV: складна, структурована поведінка — ні періодична, ні суто випадкова. Довгоживучі локалізовані структури взаємодіють складним чином. Правило 110, доведене Метью Куком тюрінг-повним у 2004 році, — найпростіший відомий універсальний комп'ютер. Правило 90 точно відтворює фрактал трикутника Серпінського.
Вольфрам дещо суперечливо стверджував, що клітинні автомати класу IV втілюють принцип «обчислювальної еквівалентності»: системи достатньої складності однаково здатні до універсальних обчислень, і саме цю еквівалентність ми називаємо інтелектом, життям і фізичним законом.
🔲 Запустіть Життя у своєму браузері: Відкрийте симуляцію Гри життя і розмістіть класичні візерунки — планер, блимач, гармату планерів. Спостерігайте за емерджентністю в реальному часі та дивіться, як три прості правила породжують нескінченну складність.
Самоорганізована критичність
Деякі клітинні автомати демонструють глибше явище: системи, що самі природним чином еволюціонують до критичного стану без будь-якого зовнішнього налаштування. Фізик Пер Бак із колегами запровадив модель піщаної купи в 1987 році як канонічний приклад.
Правила прості: додавати піщинки по одній на сітку. Коли якась клітина накопичує 4 або більше піщинок, вона «обвалюється» — перерозподіляючи по одній піщинці кожному з чотирьох сусідів. Ці сусіди можуть потім також обвалитися, потенційно запускаючи ланцюг лавин по всій сітці. Питання полягає в тому, який розподіл розмірів лавин.
Відповідь — степеневий закон: малі лавини трапляються часто, великі — рідко, але характерного розміру не існує — трапляються лавини всіх масштабів. Система самостійно еволюціонує до критичного стану, врівноваженого між порядком і хаосом, без жодного налаштування параметрів. Бак назвав це самоорганізованою критичністю (СОК).
Та сама степенева сигнатура з'являється в землетрусах (закон Гутенберга-Ріхтера), лісових пожежах, сонячних спалахах і обвалах фінансових ринків — усі це системи, що самоорганізуються до критичного стану й вивільняють накопичену напругу у безмасштабних лавинах. Чи є СОК об'єднувальним поясненням цих явищ, досі дискутується, але математична сигнатура вражаюча і повсюдна.
Клітинні автомати в природі та технологіях
Найпереконливіше підтвердження клітинних автоматів як моделей природи походить із біології. Морська равлик Conus textile має мушлю з пігментацією, разюче подібною до Правила 30 — хаотичного, начебто випадкового правила Вольфрама. Пігментні клітини равлика спілкуються лише зі своїми найближчими сусідами через хімічні сигнали, оновлюючи свій стан на основі локальних правил — точнісінько в рамках концепції КА.
Подібна динаміка, схожа на клітинні автомати, з'являється і в інших місцях:
- Серцевий м'яз: система електричної провідності серця поширює потенціали дії через двовимірний шар клітин за правилами збудливого середовища. Спіральні хвилі в такому середовищі відповідають небезпечним аритміям, як-от фібриляція шлуночків.
- Ґратково-больцманівська симуляція рідин: заміна рівнянь Нав'є-Стокса клітинним автоматом на гексагональній ґратці, де частинки рухаються та стикаються за простими правилами. Цей метод сьогодні використовується для складних симуляцій рідин в інженерії.
- Моделі транспортного потоку: модель Нагеля-Шреккенберга розглядає кожен автомобіль як клітину, що прискорюється, гальмує й випадково змінює поведінку, породжуючи реалістичні затори та хвилі «старт-стоп» без будь-якої централізованої координації.
- Моделювання росту пухлин: ракові клітини розмножуються і гинуть залежно від локальної концентрації кисню, щільності клітин і сигналізації — природна рамка КА для симуляції розвитку пухлини та оцінки стратегій лікування.
Клітинні автомати розкривають щось глибоке про природу складності: розрив між простими правилами й складною поведінкою — це не поступовий градієнт, а прірва. При певному порозі складності правил — Правило 110, Життя Конвея — система переходить у режим універсальних обчислень, і звідти можливе все.