В жизни дело идет о жизни, а не о каком-то результате ее.
И. Гете
В октябре 1970 года в уже навязшем в зубах у читателей этого курса журнале Scientific American появилась заметка известнейшего популяризатора науки, гуру головоломок и математических игр, комментатора «Алисы в Стране Чудес» Мартина Гарднера об игре «Жизнь», изобретенной знаменитым английским математиком Джоном Конвеем. Эта игра в последующее десятилетие загрузила компьютеры по всему свету так, как ни одна программа до, и вероятно, после этого.
Притягательность игры «Жизнь» состоит в том, что при гениальной простоте правил разнообразие ее вариантов поистине бесконечно.
В общем-то, игрой «Жизнь» назвать можно только условно. На самом деле, это простой клеточный автомат с комбинацией правил, подобранной таким искусным способом, что «организмы», созданные «Жизнью» не разрастаются подобно снежному кому и не умирают слишком быстро – они живут. Но лучше все-таки описать, в чем состоит эта игра.
События развиваются на двухмерной матрице (или попросту на тетрадном листе в клеточку). «Организм» представляет собой любую заданную комбинацию закрашенных клеток. Каждый ход, называемый «поколением» – это изменение состояния «организма», подчиняющееся строго заданным правилам. Правила эти необычайно просты:
если у закрашенной клетки меньше двух соседей, то в следующем поколении она «умирает от одиночества» (то есть перестает быть закрашенной);
если у закрашенной клетки больше трех соседей, то в следующем поколении она «умирает от перенаселения»;
если у пустой клетки ровно три соседа (то есть три закрашенных клетки), то в следующем поколении она «рождается» (то есть становится закрашенной).
В этом описании очень важно определить понятие «соседей» клетки. У каждой клетки 8 соседей – по одному соседу сверху, снизу, справа и слева и по одному соседу по диагонали (в левом верхнем, левом нижнем, правом верхнем и правом нижнем углу) [2]. У читателя наверняка возникает вопрос: а зачем в курсе о программировании рассматривать какую-то игру ? Причины две: во-первых, игра "Жизнь" служит чем-то наподобие сложного двойника программы "Hello World" в программировании - то есть, это такая программа, с помощью которой интересно знакомиться с тем или иным языком.
Во-вторых, "Жизнь" послужит нам в дальнейшем в качестве наглядного пособия. Мы подробно рассмотрим реализацию игры на одном из самых экзотических языков программирования - APL - в главе, посвящённой этому языку (а может быть, и ещё на каком-то другом языке впоследствии).
В-третьих... см.ниже раздел о машине Тьюринга. Короче говоря, "Жизнь" является Turing-complete computer, то есть на "Жизни" можно программировать.
Жизнь «организмов» столь разнообразна, что сравнение игры с настоящей жизнью не кажется преувеличением.
Здесь есть и устойчивые комбинации (как, например, «улей»), которые никогда не меняются, и огромные нежизнеспособные «конгломераты», умирающие через несколько поколений, и крошечные живучие организмы, или «gliders» - комбинации, находящиеся в вечном движении, или знаменитое R-pentamino – комбинация из пяти клеток, живущая больше 1000 поколений и в конце концов превращающееся в несколько «улеев», «gliders» и другие примитивные организмы. Организмы, обладающие необыкновенной живучестью называются Methuselah (по имени библейского патриарха Мафусаила, который жил 969 лет – практически жизнь R-pentamino).
Билл Госпер, хакер MIT, признанный всеми друзьями математическим гением, буквально заболел «Жизнью». Полтора года он не занимался почти ничем, кроме «Жизни». Он отнесся к игре почти с религиозным трепетом. Вот как он сам объяснял свое увлечение:
««Жизнь» позволяет заниматься наукой в новой Вселенной, там, где не все открытия уже сделаны до тебя двести или триста лет назад. Это же трагедия жизни почти каждого математика – как только он открывает что-то тут же выясняется, что Ньютон или Гаусс уже давно это придумали. «Жизнь» позволяет тебе быть первым».
Для хакера быть «богом» в своей маленькой вселенной – это и есть смысл бытия. Ничто лучше «Жизни» не отвечало такому определению. Госпер со своими друзьями проводили ночи напролет около монитора PDP-6, пробуя разные организмы «на прочность» и долговечность, делая открытия в этой незамысловатой вселенной и занося их в специальный черный блокнот, названный «The Life Scrap-book». «Мы не могли остановиться, наблюдая за организмами на экране» - вспоминает Госпер, - «мы просто сидели и смотрели на них, каждый раз загадывая заново, чем же это кончится».
Госпер открыл «шаттл» - организм, движущийся по матрице в течение нескольких поколений в одном направлении, а затем меняющий направление на противоположное.
Через еще несколько бессонных ночей, он столкнул два «шаттла» в пути и внезапно получил организм, испускающий «gliders» с постоянной частотой. Зрелище, представшее на экране, было настолько впечатляющим, что Госпер тут же распечатал «организм» на бумаге и на следующий день послал его письмом Мартину Гарднеру. Гарднер выслал Госперу 50 долларов – награду, обещанную за открытия в области «Жизни».
А вот весьма раритетная фотография машинописной страницы, на которой сам Джон Конвей собрал результаты своих "наблюдений за жизнью":
Говоря о «Жизни», нельзя не упомянуть и об Эде Фредкине – одном из основателей так называемой цифровой физики, то есть теории о том, что основной Вселенной является информация.
Теория Фредкина как нельзя лучше подходит для «Жизни». Теория утверждает, что невозможно доказать, что наша Вселенная не является в конечном итоге компьютерной симуляцией, запущенной неким хакером, находящимся в другом измерении. Госпер, основываясь на этой теории, предположил, что в достаточно большой симуляции игры «Жизнь» (настолько большой, что размеры ее будут сопоставимы с размерами Вселенной) могут возникнуть организмы, обладающие интеллектом, которые в конце концов зададутся вопросом – а не является ли их жизнь в конечном счете компьютерной симуляцией ? Если же в этой чудовищного размера программе случится «баг», интеллектуальные организмы могут столкнуться с «метафизическим» намеком из внешнего мира, приоткрывающим тайну их существования. Фредкин, в свою очередь вдохновленный таким приложением его собственной теории, предположил, что в таком случае, организмы «Жизни», пораженные встречей с их Создателем, начнут собираться в причудливый орнамент. Этот орнамент будет неким посланием на языке организмов, обращенным к создателям игры, с просьбой объяснить им, наконец, «что» они такое.
Известный философ Дэниель Деннет говорит также и о том, что в мире "Жизни" становится возможным существование Демона Лапласа - некоего существа, которое, зная положение и скорость всех частиц во вселенной, может предсказать состояние вселенной в любой момент времени её существования. (Это, конечно, очевидно, так как мы имеем дело с детерминированным клеточным автоматом).
Простые правила, как известно, могут привести к весьма неожиданным результатам и интерпретациям.
***
За долгие годы исследований у «Жизни», как и у всякой уважающей себя дисциплины, появился свой Лексикон. Если вы намереваетесь вступить в ряды бесстрашных исследователей этой бесконечной, но дискретной Вселенной, вам просто необходимо ознакомиться с некоторыми основными понятиями из Лексикона.
Oscillator: так называется организм, который через несколько поколений возвращается к своему первоначальному виду. На рисунке показан один из первых осцилляторов, найденный самим Конвеем, который называется «маяк»:
Spaceship: организм, который возвращается к первоначальному виду через несколько поколений, но уже в другом месте (то есть, spaceship – это oscillator, движущийся в пространстве). Наиболее известны такие spaceships, как glider, Канадский Гусь, Орион, Улитка, Лебедь, Черепаха, Оса и другие. На рисунке изображен spaceship под названием dart:
Glider: Самый маленький из известных spaceship’ов. Был открыт Ричардом Гаем в 1970-м году, когда группа под руководством Конвея исследовала поведение R-pentamino:
Puffer: Организм, движущийся в пространстве как spaceship, но оставляющий позади кучи мусора.
Gun: Организм, постоянно испускающий spaceships. Самый маленький из известных науке guns называется Gosper Glider Gun (тот самый, за который он получил премию от Мартина Гарднера в ноябре 1970):
Still life: Стабильный, не меняющийся организм. Вот некоторые примеры still life:
Boat: Единственная устойчивая конфигурация (still life) из 5 клеток (на рисунке выше).
Garden of Eden: Конфигурация клеток, которая возможна только в нулевом поколении, то есть не может быть получена из какой-либо другой конфигурации. Теорема Эдварда Мура гарантирует существование таких конфигураций для широкого класса клеточных автоматов, включая «Жизнь». Джон Конвей предпочитает термин orphan (сирота).
Soup: Так называется любая случайная начальная конфигурация клеток «Жизни».
Replicator: Организм, постоянно создающий копии самого себя. Известно, что репликаторы существуют, но ни одного пока не найдено .
Eater: Стабильная конфигурация (still life), которая может взаимодействовать с движущимися организмами, не неся при этом потерь. Вот eater, найденный Госпером, под названием "рыболовный крючок":
Breeder: Организм, растущий с квадратической скоростью. Самый маленький из известных breeders, состоящий из 52 клеток, называется metacatacryst.
***
В 2000 году в жизни "Жизни" произошло событие исключительной важности. Пол Ренделл (Paul Rendell) сконструировал конфигурацию, имитирующую машину Тьюринга[3]. Основная работа была проделана между 99-м и 2000 годами, но в общей сложности Ренделл посвятил этой поистине монументальной конфигурации около двадцати лет. Перед вами сильно уменьшенная машина Тьюринга, созданная на основе "Жизни":
Эта конкретная машина выполняет простое действие – удваивает число единиц на ленте. Например, при вводе 11, машина через 16 циклов выдаст 1111. Как пишет сам Ренделл (в 2000 году) эта программа выполняется на его компьютере в течение часа. Неплохо для того, чтобы выдать четыре единицы вместо двух даже для 2000-го года!
«Машина» Ренделла, представленная на рисунке, состоит из множества взаимодействующих между собой частей. Одно их описание способно доставить удовольствие:
Column Address, Comparator, Control Conversion, Copy Unit, Finite State Machine, Memory Cell, Metamorphosis, Next State Delay, Not Xor Gate, Output Collator, Pop Control, Push Control, Row Address, Set Reset Latch, Signal Detector, Stack, Stack Cell, Turing Tape и многое другое.
Так, например, выглядит Memory Cell:
А вот NOT XOR Gate:
Впечатлились? А теперь вперёд - программировать "Жизнь" на самом экзотическом языке программирования в мире!
[1] "La Vie mode d'emploi" - Название весьма удивительного романа французского писателя Жоржа Перека, члена группы УЛИПО (Кое-что об Улипо см. ещё в этом посте). Рекомендуется к немедленному прочтению всем слушателям данного курса.
[2] Эта комбинация соседей называется "окрестностью Мура", в отличие от "окрестности фон Неймана", состоящей только из четырёх соседей (без диагональных).
[3] Здесь предполагается длинное отсутпление (или даже целая глава о машине Тьюринга), но об этом как-нибудь в другой раз.