Мне нравится решето, смоделированное в игре «Жизнь», поскольку из древнегреческого математического инструмента оно превратилось в межгалактическую перестрелку между флотилиями глайдеров и космических кораблей. Наблюдать за данной конфигурацией — это как будто смотреть батальную сцену в фантастической эпопее или, возможно, отслеживать эволюцию колонии муравьев, поведение которых носит сугубо математический характер. Не забывайте: как только вы построите исходную конфигурацию, вам не нужно вмешиваться в дальнейший процесс. Эта фигура может продолжать свою жизнь до бесконечности, отстреливая космические корабли и оставляя в живых лишь те из них, порядковый номер которых представляет собой простое число.
«Уровень мастерства реально поражает, — сказал Госпер о самых лучших конфигурациях. — Люди, которые пытаются [создавать фигуры], быстро осознают, насколько это сложно, а удачные образцы приводят их в неописуемый восторг. Для того чтобы сосредоточиться на игре в достаточной степени, нужно находиться почти в состоянии невменяемости». За период с семидесятых годов до наших дней построены сотни удивительных конфигураций, в том числе и вычисляющая значение числа π, которую изобрел британский подросток по имени Адам Гаучер. К чему еще стремиться? «Жизнь — неистощимый источник вопросов и задач», — резюмировал Госпер.
Игра «Жизнь» подвергает сомнению наши предвзятые представления о том, как работает этот мир, поскольку она показывает, как простой набор локальных правил может генерировать невероятно сложное общее поведение. При взгляде на такую идеально интегрированную систему, как решето Эратосфена, удивляет то, что каждая клетка взаимодействует всего с восемью соседними клетками.
Игра «Жизнь» демонстрирует также существование разных реальностей на разных уровнях игры. Решето Эратосфена — это конфигурация, разработанная на основе физических свойств глайдерных ружей с использованием технологии столкновений и космических кораблей. Однако на более детальном уровне таких вещей, как «столкновение» или «космический корабль», нет. Есть лишь неподвижные клетки, которые могут быть либо «живыми», либо «мертвыми».
По мере создания все более сложных фигур возникает вопрос: каков предел того, что может сделать конфигурация в игре «Жизнь»? Да буквально все, на что способен ваш ПК, планшет или смартфон. Если задача выполнима с помощью компьютера, тогда это можно сделать и посредством конфигурации в игре «Жизнь».
Конвей доказал истинность этого утверждения, продемонстрировав, что можно создать компьютер «Жизни», другими словами — исходную конфигурацию живых клеток, имитирующую внутреннюю схему компьютера. Вам придется поверить мне на слово (или прочитать книгу по информатике), но внутренняя схема компьютера на базовом уровне состоит из следующих компонентов: проводники, логические элементы и регистр памяти. Генератор тактовых импульсов порождает электронные импульсы, представляющие двоичные числа. Наличие импульса — это 1, а его отсутствие — 0. Конвей понял, что глайдеры могут выполнять функции импульсов, передающихся по проводникам. Следовательно, поток глайдеров может представить любое число, состоящее из нолей и единиц, как показано на рисунке ниже. Поскольку глайдеры двигаются по диагонали, я разместил сетку под углом 45 градусов.
Поток глайдеров
Конвей разработал логический элемент простейшего типа, выполняющий операцию НЕ (операцию отрицания) [7]. Логический элемент — это устройство, имеющее несколько входов и выходов. У логического элемента, выполняющего операцию НЕ, только один вход и один выход. Сигнал на выходе противоположен сигналу на входе: он меняется с 1 на 0 и с 0 на 1. Следовательно, логический элемент отрицания в игре «Жизнь» должен превратить наличие глайдера во входящем потоке в его отсутствие в исходящем потоке и наоборот. Конвей понял, что эту функцию может выполнить стратегически правильно размещенное глайдерное ружье, как показано на рисунке ниже. Входящий поток перемещается горизонтально, слева направо. Глайдерное ружье стреляет по глайдерам вертикально вниз. Если во входящем потоке появляется глайдер, его уничтожает глайдер, порожденный ружьем. Но если во входящем потоке глайдера нет, глайдер из ружья проходит невредимым, поскольку ему не с чем сталкиваться. Таким образом, исходящий поток содержит 1, если входящий поток содержит 0, и 0 — если 1. Это и есть логический элемент, выполняющий операцию НЕ. Исходящий поток находится под прямым углом к входящему потоку, но это не имеет значения, так как мы можем изменить направление потока в дальнейшем в случае необходимости.
Все логические элементы выполняют операции трех базовых типов: НЕ, И и ИЛИ. Конвей сконструировал также состоящие из ружей и пожирателей конфигурации, имитирующие логические элементы для операций И и ИЛИ. Он показал, что можно сделать так, чтобы потоки глайдеров меняли направление движения, что моделировало изгибы проводников. Конвей также продемонстрировал, как сделать потоки глайдеров разреженными, чтобы два потока могли пересечься, избежав при этом столкновения глайдеров, что изображало пересечение проводников. Кроме того, он показал, как сделать регистр памяти из блоков. Каждый блок представляет собой какое-то число в зависимости от его расстояния от определенной точки. Глайдеры, которые врезаются в блок, перемещают его ближе к этой точке или дальше от нее, меняя значение блока. Это подтвердило правильность выдвинутой Конвеем гипотезы: построив в игре «Жизнь» проводники, логические элементы и регистр памяти, он доказал, что игра, ставшая его математическим хобби, теоретически способна (при наличии достаточно большой сетки) имитировать любой существующий в нашем мире компьютер.
Получив приведенное выше доказательство, Джон Конвей потерял интерес к игре «Жизнь». (В 1986 году он переехал в Принстон, чтобы возглавить кафедру математики вместо Джона фон Неймана.) Однако многие ее поклонники были настолько ею увлечены, что у них появилась зависимость, которая со временем лишь усиливалась. Международное сообщество любителей игры «Жизнь» насчитывает около сотни членов; к их числу относился и Пол Чэпмен, решивший на рубеже столетий построить компьютер в игре «Жизнь». «Знать, что что-то можно сделать, и сделать это — совершенно разные вещи», — заявил он.
Логический элемент отрицания содержит ружье, которое выстреливает в глайдеры, движущиеся перпендикулярно входящему потоку
Подобно многим любителям игры «Жизнь», Пол не был научным сотрудником. В 1970-х он изучал математику в Кембридже (и слушал лекции Конвея), а затем стал консультантом по информационным технологиям. В настоящее время Пол живет в центре Лондона, неподалеку от ресторана, в котором мы с ним встретились. Он предпочел столик на улице, несмотря на плохую погоду, поскольку ему не нравился запрет на курение внутри заведения. Когда мы разговаривали, Пол скручивал собственные сигареты. «Я люблю “Жизнь” потому, что она полна сюрпризов, — признался он. — Каждый раз, когда вы ищете способ сделать что-то лучше, вы найдете десятки таких способов».
У обычного компьютера есть аппаратное и программное обеспечение; точно так же и созданная в игре «Жизнь» конфигурация, имитирующая работу ПК, имела «железо» и «программы». Первое моделировало кабели машины, а второе — программу, которую она должна читать. В своем прототипе компьютера в игре «Жизнь» Пол использовал не созданную Конвеем сеть из ружей, глайдеров и пожирателей, а более современную и эффективную технологию, основанную на исходном шаблоне из семи клеток под названием «Гершель». Его конфигурация состояла из нескольких миллионов живых клеток и программы, содержащей инструкции по поводу того, как вычислить сумму 1 + 2. «Для поиска суммы 2 + 3 понадобилось бы слишком много времени», — объяснил Пол. Конфигурация начиналась с космического корабля, поражающего устойчивую фигуру, которая порождала сигнал о столкновении с разными элементами, а те, в свою очередь, порождали другие сигналы, и маршрут перемещения сигналов по всей системе напоминал гигантскую игру в одну из разновидностей бильярда. В конце концов блок в регистре вывода показывал число 3. «Я был в восторге, — сказал Пол. — Если я могу сложить один и два, это говорит о том, что эта же машина может рассчитать миллионную цифру числа π, управлять системой Windows или, если ввести правильные параметры, смоделировать жизненный цикл звезды!»
Безусловно, компьютер, построенный Полом в игре «Жизнь», был неприменим на практике для выполнения всех этих задач. Но он вернул «Жизнь» к ее истокам. Джон фон Нейман выдвинул идею клеточного автомата во время изучения процесса самовоспроизведения. Конфигурация Пола открыла заманчивую возможность создания самовоспроизводящихся сущностей в игре «Жизнь».
Безусловно, компьютер, построенный Полом в игре «Жизнь», был неприменим на практике для выполнения всех этих задач. Но он вернул «Жизнь» к ее истокам. Джон фон Нейман выдвинул идею клеточного автомата во время изучения процесса самовоспроизведения. Конфигурация Пола открыла заманчивую возможность создания самовоспроизводящихся сущностей в игре «Жизнь».
На первый взгляд фигуры, эволюционирующие на решетке игры «Жизнь», кажутся живыми, так как по мере смены поколений они трансформируются и меняют направление. Однако для того, чтобы некий объект действительно был живым, он должен обладать способностью к самовоспроизведению. Но что это такое? Глайдер, например, воспроизводит себя достаточно просто. Это состоящая из пяти клеток фигура, которая каждые четыре поколения возвращается в исходную форму, сместившись на одну клетку вниз и одну в сторону. Фон Нейман хотел знать, как машина может построить точную копию самой себя. Для того чтобы это понять, ему предстояло решить математическую головоломку, поскольку механическая сторона процесса самовоспроизведения содержит один логический парадокс.
Мы с вами уже говорили о том, что компьютеры состоят из аппаратного и программного обеспечения. Давайте назовем аппаратное обеспечение «конструктором», а программу, которую мы вводим в конструктор, чтобы он построил копию себя, — «макетом». Мы рассчитываем на то, что после ввода макета конструктор воспроизведет новый конструктор вместе с новым макетом, по сути, создав копии двух исходных элементов. Но здесь возникает вопрос: содержит ли макет инструкции относительно создания нового макета? Если да, тогда они должны также содержать инструкции по поводу создания нового макета, который, в свою очередь, должен содержать инструкции по поводу того, как создать инструкции в отношении построения нового макета — и так далее до бесконечности. В итоге мы получаем бесконечную регрессию инструкций, содержащихся в данном макете, что недопустимо, поскольку макет должен быть конечным. С другой стороны, если макет не включает никакую информацию о себе, машина не сможет себя полностью воссоздать, поскольку в новой машине нет макета. Прежде чем думать о технической стороне дела, фон Нейману следовало разобраться с математикой.
В итоге фон Нейман пришел к такому выводу: для того чтобы машина могла воспроизвести себя, необходимо ввести в систему новый элемент, который бы воссоздавал макет, другими словами — устройство для копирования макета. Таким образом, когда конструктор считывает макет, он строит новую машину, совершенную во всех отношениях, кроме одного — в ней нет макета. На последнем этапе устройство копирования должно создать копию макета и отправить ее в новую машину. Следовательно, самовоспроизводящаяся машина фон Неймана использует макет двумя разными способами: конструктор читает его как набор инструкций, а копировальное устройство создает его копию. Только применение макета один раз в качестве программы, а другой — в качестве объекта позволило решить чрезвычайно трудную проблему бесконечной регрессии.
Конфигурация, созданная фон Нейманом для своего первого клеточного автомата, состояла из конструктора, устройства копирования и макета. Теоретически он показал, что она способна к самовоспроизведению, но не продемонстрировал этого на практике, поскольку компьютеры тогда еще не были достаточно мощными для этого. Тем не менее работа фон Неймана оказала заметное влияние на целое поколение специалистов в области вычислительных машин и систем, философов и даже биологов, которые изучали в 1950-х годах механизм репродукции живых клеток. Когда на протяжении этого и следующего десятилетия им все же удалось раскрыть специфику данного механизма, они обнаружили, что фон Нейман прав! В свое время он создал абсолютно точную модель самовоспроизведения живых организмов. В каждой клетке есть макет (ее ДНК), содержащий закодированные инструкции по репродукции новых клеток. Однако в ДНК нет описания самой ДНК — та ДНК, которая появляется в новой клетке, представляет собой результат копирования (двойная спираль ДНК делится на две части, а ферменты создают две точные копии исходной ДНК). Подобно тому как машина фон Неймана прочитывает макет двумя способами, ДНК также ведет себя по-разному в процессе воспроизводства живой клетки.
Пол Чэпмен попытался построить самовоспроизводящуюся конфигурацию клеток, но не смог найти способ копирования макета. И вот в 2010 году канадский программист Эндрю Уэйд объявил о создании космического корабля «Джемини». «Когда я впервые увидел его, я пришел в восторг! — воскликнул Пол. — “Джемини” — это самая важная фигура за все сорок лет. И никто даже не знал, кто такой Эндрю Уэйд! Он просто написал об этом на доске объявлений!»
«Джемини» — первая самовоспроизводящаяся конфигурация в игре «Жизнь». Как показано на рисунке ниже, эта фигура имеет форму очень длинной и тонкой гантели, на концах которой находятся идентичные конструкторы (отсюда название «Джемини» — «близнецы»), а между ними на решетке размером 4 миллиона × 4 миллиона клеток расположен макет, состоящий из глайдеров. Оригинальная идея Уэйда заключалась в том, чтобы вместо создания копий макета обеспечить его быстрое перемещение между двумя конструкторами. Когда макет достигает одного из конструкторов, он дает ему указание построить свою новую версию на 5120 клеток вверх и 1024 клетки в сторону и одновременно уничтожить себя. После этого макет отправляется в обратном направлении, где через миллионы клеток достигает противоположного конструктора и тоже дает ему указание построить свою новую версию на 5120 клеток вверх и 1024 клетки в сторону, а затем саморазрушиться. Этот цикл, после которого вся конфигурация смещается на 5120 клеток вверх и 1024 клетки в сторону, повторяется каждые 33,7 миллиона поколений. Поскольку конфигурация «Джемини» двигается, ее считают космическим кораблем, но она двигается не посредством кувырков, как это делает глайдер, а с помощью процесса самовоспроизведения. «Самое блестящее, что сделал Эндрю Уэйд, — сказал Пол, — это устранил этап создания копии [макета] и сделал так, что [макет] просто появляется как гром среди ясного неба, причем в самый подходящий момент для того, чтобы дать инструкции».
«Джемини» — это первый космический корабль, движение которого основано на самовоспроизведении
С «Джемини» связано еще одно важное достижение: это первый космический корабль, который перемещается наискось, то есть не в горизонтальном и не в вертикальном направлении и не под углом 45 градусов к сетке.
Пол показал мне лист бумаги с изображением одного из конструкторов «Джемини». Он с гордостью упомянул о том, что в его основу положен компьютер, созданный им в игре «Жизнь». Изображение конструктора напоминало кляксу, состоящую из группы серых шевронов в окружении крохотных точек. Я спросил Пола, есть ли у него изображение всего корабля «Джемини». Он ответил, что в этом нет смысла, поскольку в таком масштабе эта фигура была бы настолько разреженной, что оказалась бы практически невидимой. Почти вся конфигурация представляет собой поток глайдеров. Как ни странно, макет занимает намного больше места, чем конструктор. В клеточном автомате фон Неймана тоже присутствовал подобный дисбаланс: его конструктор помещается в сетку 97 × 170, тогда как макет имеет длину 145 315 клеток. Крупные конфигурации состоят в основном из пустого пространства. «Возможно, в игре “Жизнь” так много пустого пространства по той же причине, почему его так много в нашем мире, — пояснил Пол. — У атомов должно быть достаточно места для того, чтобы они выполняли свою работу».
Появление «Джемини» усилило ожидания в отношении следующего этапа исследования игры «Жизнь» [8]. Если исходная конфигурация порождает копии, в которых есть небольшие отличия от оригинала, это может обусловить дарвиновский естественный отбор. В 1982 году Джон Конвей выдвинул предположение о том, что если бы решетка игры «Жизнь» была достаточно большой и в исходном состоянии клетки располагались на ней в случайном порядке, то «через приличный промежуток времени появились бы разумные существа, способные к воспроизводству». Три десятилетия спустя эта гипотеза Конвея по-прежнему будоражит кровь любителям игры «Жизнь». Самую интересную работу выполняет Ник Готтс, специалист по комплексным системам из Абердина (Шотландия), который ищет новые конфигурации, заполняя сетку игры «Жизнь» живыми клетками в произвольном порядке. Он называет свой проект «рассеянной Жизнью», поскольку относительная доля живых клеток должна быть довольно низкой по сравнению с количеством мертвых клеток, иначе это приведет к слишком большому числу неконтролируемых взаимодействий. «В некоторых конфигурациях присутствует нечто, напоминающее естественный отбор, — объясняет Ник. — Есть конфигурации, регулирующие появление других конфигураций аналогичного типа. Я убежден, что, если бы моя программа выполнялась достаточно долго, вступил бы в действие закон естественного отбора».