Візьміть просте загратоване простір. Задайте набір нехитрих правил. Запустіть час. Ви отримали клітинний автомат - майже що цілий світ.
Кубічна всесвіт Minecraft щільно заселена - продана в кількості більше 70 млн копій гра входить до трійки найуспішніших в історії. Тут є практично все: грунт і мармур, дерева і лава, хитромудрі елементи для спорудження складних машин і механізмів. Вибираючи будівельні куби, учасники зводять, змінюють і доповнюють цей світ, складають великі керівництва і поради по конструюванню - і проходять онлайн-тести на тему «Перевір, чи не занадто ти пристрастився до Minecraft». Дійсно, цей світ затягує, адже він живе і еволюціонує.
Якщо освітлення достатньо, кубічний блок ґрунту, що має по сусідству блок зеленого лужка, теж проросте травою. Блок води знизить рівень і розтечеться на сусідні ділянки, якщо перед ним не буде перешкод. При доступі до води і сонячного світла урожай зростає на один рівень з кожної итерацией тимчасового циклу. Остигаючи, блок розплавленої лави видозмінюється за простими правилами: лава (нерухома) стає обсидіаном, якщо верхній блок - вода; лава (поточна) стає каменем, якщо один із сусідніх блоків - вода.
Типові структури, що виникають в «Життя» Конвея. Якщо гра починається з випадковою конфігурації, швидше за все, вона закінчиться появою стійкого набору таких живучих форм. Але в загальному випадку еволюція системи непередбачувана, і щоб з'ясувати, чим закінчиться така «Життя», потрібно її «прожити», тобто змоделювати.
Незважаючи на грубі кубічні форми, всесвіт Minecraft вражає різноманітністю і складністю, які виростають не тільки з вільного творчості гравців, але і з набору простих принципів, які визначають хід її еволюції. Це справжня матриця, хіба що тривимірна, і її осередки оновлюються цикл за циклом, в залежності від дій гравця і локального оточення. Якщо не справжній картатий світ, то - клітинний автомат.
Правила життя"
«Життя» існує на нескінченній гратчастої площині. Кожна клітина, що має двох або трьох живих сусідів, виживає на наступному кроці часу. Якщо їх менше або більше, клітина вмирає від «самотності» або від «перенаселення». Якщо у мертвої клітини три живих сусіда, вона стає живою. Враховується сусідство по вертикалі, горизонталі та діагоналі. Ось і все: базові принципи гри виключно прості, але можуть породжувати дивно складну поведінку і різноманітність форм.
Планер (глайдер) - переміщається конфігурація з п'яти клітин
Правила «Життя» були опубліковані кембріджським математиком Джоном Конвеем в 1970 році і відразу зробили клітинні автомати неймовірно популярними. Тисячі ентузіастів, відчувши себе в ролі володарів цього картатого маленького світу, почали досліджувати двовимірні форми, які народжуються і вмирають в ньому. Серед них виявилися стаціонарні «натюрморти», здатні існувати вічно без будь-яких змін; періодичні «осцилятори», що повторюють одні й ті ж фігури з певною циклічністю; рухомі «планери», які з кожним ходом зміщуються в тому чи іншому напрямку.
Сьогодні в «Життя» відомі мільйони таких істот: зі зростанням «розмірів», тобто числа осередків, кількість можливих «натюрмортів» і «осциляторів» збільшується стрімко. Але вже в перші роки повального захоплення цим витонченим клітинним автоматом з'ясувалося, що при наявності достатнього «життєвого» простору в ньому можуть існувати і набагато більш складні структури. Наприклад, «міцний горішок» складається з семи живих клітин, які болісно виживають протягом 130 поколінь, після чого всі разом анігілюють.
Автомат стає машиною
Сам Конвей припускав, що така смертна доля чекає будь-яку нестаціонарну і неперіодичних форму «Життя», і навіть оголосив символічну премію тому, хто зможе довести або спростувати ідею про те, що на цьому картатому поле можливо нескінченне розмноження. Однак з обіцяної сумою в $ 50 йому довелося розлучитися досить швидко. У тому ж 1970 році Білл Госпер виявив періодичну структуру - «рушниця», яке кожні 30 кроків повертається до початкової конфігурації, народжуючи що летить у бік «планер». А ось це вже дуже і дуже цікаво ...
Подібні «планерні рушниці» можна розглядати як генератори імпульсів, якими обмінюються логічні елементи будь-якої обчислювальної машини: пішов планер - одиниця, планера немає - нуль. Якщо пара таких планерів зіткнеться під прямим кутом, то один з них анігілює, що дозволяє моделювати логічний елемент НЕ. Більш складними способами можна створити і інші елементи, які виконують всі базові логічні операції, включаючи І і АБО. Залишається їх скомбінувати - і гра стане обчислювальним пристроєм.
Втім, той факт, що деякі клітинні автомати здатні виконувати будь-які математичні операції, емулюючи універсальну машину Тьюринга, був відомий і до Конвея: в 1950-х цим скористався великий Джон фон Нейман. На хвилі загальної любові до робототехніці вчений задався питанням, чи можливо сконструювати робота, який міг би нескінченно самовідтворюватися, штампуючи власні копії, щоб вони, в свою чергу, без кінця виробляли нові покоління роботів.
«Планерне рушницю» - основа багатьох комбінацій, які втілюють логічні елементи обчислювальної машини. Такі великі зміни автомата Конвея здебільшого складаються з порожніх клітин. З цього приводу математик Пол Чепмен зауважив: «Можливо, в« Життя »так багато пустого простору з тієї ж причини, по якій його так багато і в нашому житті. Атоми повинні мати достатньо місця для того, щоб робити свою роботу ».
нескінченне народження
Проектувати такий апарат з металевої плоті і електричної крові було б справою явно невдячним. Але питання досить було вирішити на принциповому, математичному рівні, так само, як кількома десятиліттями до того надійшов з обчислювальною машиною той же Тьюринг. Ідею фон Нейманом підкинув колега по Лос-Аламоської національної лабораторії Станіслав Улам, який використовував клітинні автомати для досліджень зростання кристалічних структур. Фон Нейман підібрав такий простір нескінченної «шахівниці», яке здатне імітувати машину Тьюринга, і описав для неї конфігурацію приблизно з 200 000 клітин, здатну самовідтворюватися нескінченною низкою поколінь. Закони, що керують еволюцією такого клітинного автомата, набагато складніше, ніж у «Життя», - досить згадати, що осередки його можуть приймати 29 різних значень, і для кожного переходу між ними потрібно окреме правило. Зате сусідами - околицею кожного осередку - в автоматі фон Неймана вважаються лише ті чотири, що розташовані по вертикалі і горизонталі від неї, тоді як у Конвея враховуються цілих вісім осередків, в тому числі і що знаходяться по діагоналі від вихідної (околиця Мура).
Локальна залежність поведінки осередків - таке ж фундаментальне властивість клітинних автоматів, як і глобальність правил, які діють абсолютно однаково в будь-якій точці сітки. Це нагадує реальний світ: наскільки нам відомо, закони фізики однакові в будь-який його точці, а ось взаємодії поширюються з кінцевою швидкістю, максимально - світловий. У світі клітинних автоматів цю межу швидкості ще помітніше. Будь-які зміни в «Життя» в принципі не можуть відбуватися швидше швидкості шахового короля - на одну клітку за один інтервал часу. Взагалі, незважаючи на уявну простоту клітинних автоматів, процеси, які відбуваються в них, у своїй математичній основі часто виявляються аналогічні реальним.
Хижаки і жертви
Візьміть склянку води і вилийте її на стіл. Кращий з доступних способів передбачити її рух - використовувати суперкомп'ютер, хоча і він здатний дати лише приблизне рішення заплутаних рівнянь гідродинаміки. Але той же процес можна уявити і в вигляді спрощеної моделі «граткової газу», осередки якого можуть містити або не містити молекул. Це дозволить описати їх поведінку за допомогою набору коротких правил. Наприклад: протягом захоплює молекулу вниз, поки вона не зустріне перешкоду - стіл або іншу молекулу, - в цьому випадку вона переміщається в випадкову незайняту клітинку збоку. Ми отримаємо нехитрий клітинний автомат, який здатний з прийнятною точністю імітувати реальність.
«Сади Едему» - один з варіантів конфігурації клітинного автомата, які не можуть з'явитися в результаті еволюції і повинні бути задані із самого початку, з «створення» цього штучного маленького світу.
Схожі правила дозволяють моделювати поведінку натовпу. Якщо є можливість, людина рухається вперед; зустрівши перешкоду, поверне в бік; якщо на всі боки стоять інші люди, залишиться на місці. Околиця в цьому випадку доведеться враховувати більш далеку, ввівши ймовірність переміщення в тому чи іншому напрямку в залежності від присутності інших людей або стін - «дивлячись» на кілька клітин вперед. Варіюючи ці параметри, можна з точністю моделювати рух людського потоку і використовувати ці результати при проектуванні міського простору.
Існують клітинні автомати, які моделюють коливальні хімічні реакції і роботу дихальних продихів рослинного листа, турбулентні процеси і утворення узору на раковинах молюсків, динаміку чисельності популяцій травоїдних і хижаків. Правила прості. Особина може переміститися на випадкову з клітин в околиці Неймана. З певною періодичністю вона залишає в вихідної клітці нащадка, з певною - сама вмирає від старості. Хижа особина може проковтнути сусіднє травоїдна, а якщо не зробить цього протягом деякого часу, то загине від голоду. Такий клітинний автомат дозволяє отримати характерні S-образні криві популяційного зростання: чисельність хижаків і травоїдних вийде на певний рівень і буде коливатися біля нього. Все як в житті.
Еволюцію одновимірного клітинного автомата можна уявити на площині, одним з вимірів якої буде час. Один з таких автоматів створює фрактальну структуру «серветки Серпінського».
картатий світ
Схожість життя з клітинними автоматами давно інтригує вчених. Ці ідеї максимально розвинені у Конрада Цузе, а пізніше - у Едварда Фредкіна, який сформулював свою «кінцеву гіпотезу»: «Будь-яка фізична величина, включаючи час і простір, є кінцевою і дискретної». Квантуемого простору-часу залишається недоведеною, однак на ці уявлення спираються деякі цілком шановні теорії, включаючи петлеву квантову гравітацію.
Звідси залишається зробити останній крок. Якщо Всесвіт уявити як дискретне поле, осередки якого змінюються відповідно до визначених законами, то чи не є вона по суті клітинним автоматом? Робота його створює ілюзію існування частинок, полів і взаємодій, які насправді - лише різні стани дуже маленьких «елементарних осередків» світобудови, що змінюються за надзвичайно короткі проміжки часу.
Матриця «шахівниці» Конвея перетворюється в глобальну матрицю нашого світу - динамічну і зачаровує. Втім, погляди «цифровий фізики», головним апологетом якої сьогодні виступає Стівен Вольфрам, не можна назвати загальноприйнятими серед вчених. «Монітор вашого комп'ютера, зображення на якому складається з точок-пікселів, доводить, що такий світ може виглядати цілком реалістично, - пише нобелівський лауреат Френк Вільчек. - Але в ньому обов'язково щось буде трохи не так ».
Стаття «Автоматична життя» опублікована в журналі «Популярна механіка» ( №3, Лютий 2016 ).
Якщо Всесвіт уявити як дискретне поле, осередки якого змінюються відповідно до визначених законами, то чи не є вона по суті клітинним автоматом?