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