В промозглый лондонский день я отправился на встречу с одним человеком, чтобы поговорить о космических кораблях. Пол Чэпмен сидел на террасе итальянского ресторана в темном пальто, а его панама сияла оранжевым цветом под излучением инфракрасного обогревателя. Темные брови нависали над большими очками без оправы, а лицо заросло взлохмаченной седой бородой. Пол принадлежит к единственной в своем роде группе людей, увлекающихся математической игрой под названием Game of Life («Жизнь»). Ему не терпелось рассказать мне о своем последнем открытии.

«Новость, достойная газетной статьи, — заявил Пол, вынимая из кармана черную записную книжку и разворачивая истрепанный лист бумаги. — Я ношу это с собой повсюду». Игру «Жизнь» изобрел сорок лет назад молодой преподаватель Кембриджского университета Джон Конвей, разработавший законы вымышленной вселенной, согласно которым конфигурации клеток квадратной решетки эволюционируют и мутируют самыми завораживающими и непредсказуемыми способами. Сейчас в этой вселенной существуют такие фигуры, как «фитили», «ружья», «паровозы» и «космические корабли». На листике Пола было изображение космического корабля «Джемини», состоящего почти из миллиона крохотных клеток и представляющего собой одну из самых крупных и сложных фигур, когда-либо построенных в игре «Жизнь». «Джемини» напоминал ромбовидный алмаз, образованный из нескольких «елочных» шаблонов. Пол нетерпеливо показывал на разные фрагменты этого корабля, объясняя, почему он такой особенный. «Джемини» — это первая самовоспроизводящаяся фигура, которая способна построить свою точную копию. Этот космический корабль живой. В конце концов жизнь породила жизнь. «Это удивительно, — воскликнул Пол. — За сорок лет мы еще не видели ничего подобного».

Мысль о том, что математическая квадратная решетка позволяет создать конфигурацию, достойную серьезных размышлений, восходит как минимум к так называемому решету Эратосфена, названному так по имени древнегреческого ученого-энциклопедиста, который, как мы с вами знаем, сделал первую достаточно точную оценку размеров Земли. Решето Эратосфена — это алгоритм поиска простых чисел. Мы начинаем отсчет по возрастанию с 1 и, достигнув первого подходящего числа, удаляем из списка все числа, кратные данному числу. (Этот метод очень похож на подход Джерри Ньюпорта, человека с синдромом гения, о котором шла речь в главе 1.) Первое простое число — 2, поэтому мы должны вычеркнуть из списка все четные числа. Второе простое число — 3, поэтому нам необходимо вычеркнуть все числа, кратные трем. Число четыре уже было вычеркнуто, поскольку оно четное, а значит, следующее простое число — 5 и т. д.

Решето Эратосфена для чисел от 1 до 100 можно представить в виде сетки с шестью рядами, как показано на рисунке ниже. Горизонтальные линии, проведенные по ряду после числа 2, а также по рядам, начинающимся с чисел 4 и 6, вычеркивают все четные числа, а линия после числа 3 — числа, кратные 3. Два набора диагональных линий вычеркивают числа, кратные 5 и 7. Больше никаких линий не нужно, поскольку, если в поисках простых чисел вы просматриваете список до числа n, вам нужно искать числа, кратные простым числам, которые не превосходят значения √n. В данном случае n = 100, поэтому мы можем прекратить поиск чисел, кратных простым, как только доберемся до числа 10.

Решето Эратосфена

Это очень красивая и наглядная решетка, так как она сразу же говорит вам, что все простые числа должны находиться в первом и пятом рядах, а значит, они все либо на единицу больше, либо на единицу меньше числа, кратного 6. Однако самый важный момент, на который необходимо обратить внимание, — это причина, вынуждающая нас отсеивать числа: простые числа не появляются в каком-либо предсказуемом порядке. Если бы мы продолжили строить эту решетку до бесконечности, они были бы разбросаны в случайном порядке по первому и пятому рядам. Тот факт, что простые числа настолько легко найти, но их распределение столь непредсказуемо, — одна из самых ранних и наиболее непостижимых неожиданностей в математике.

В 1963 году 54-летний Станислав Улам отвлекся от лекции, на которой присутствовал, и принялся машинально чертить что-то на листе бумаги. Он нарисовал сетку из горизонтальных и вертикальных линий и стал нумеровать образованные путем их пересечения клетки, начав с единицы в центре и двигаясь по спирали. Наверное, ему было действительно скучно, потому что после этого он отметил все простые числа кружочками. Мы знаем, что простые числа не подчиняются очевидной закономерности, так что такого там увидел Улам? Как ни странно, он заметил нечто весьма неожиданное. Простые числа выстраивались вдоль диагональных линий (см. рисунок ниже), создавая рисунок, известный сегодня как спираль Улама. Когда Улам запрограммировал компьютер на построение такой спирали от 1 до 65 000, там тоже образовались диагонали, а также горизонтальные и вертикальные теневые области. Спираль Улама позволяет сделать волнующее предположение о том, что за беспорядочным шумом можно обнаружить музыку.

Улам был одним из польских математиков, которые в 1930-х годах во Львове принимали участие в создании «Шотландской книги». В 1935 году Джон фон Нейман, математик венгерского происхождения из Института перспективных исследований в Принстоне, пригласил Улама в США, куда тот и переехал навсегда в 1939 году. Четыре года спустя фон Нейман сделал Уламу, работавшему тогда в Висконсинском университете, более интригующее предложение: перебраться в Нью-Мексико и присоединиться к нему в работе над неизвестным проектом. Улам взял в университетской библиотеке путеводитель по штату Нью-Мексико и увидел, что до него путеводитель брали его коллеги, которые исчезли куда-то без всяких объяснений. Выяснив, в каких областях они работали, он понял, что именно его просят сделать.

Так Улам присоединился к Манхэттенскому проекту в Лос-Аламосе, где сыграл ключевую роль в разработке термоядерного оружия, а также создал новый раздел математики. Он понял, что если поведение физической системы является слишком сложным, то для того, чтобы его прогнозировать, нужно предоставить компьютеру возможность сделать множество случайных оценок, а затем получить более точные показатели с помощью статистических методов. Во время одной из поездок на автомобиле Улам объяснил этот метод фон Нейману; тогда и было придумано для него название — «метод Монте-Карло». Например, для того чтобы определить вероятность того, что шарик рулетки остановится на черном, игроку не нужно решать уравнение — он может просто подсчитать, сколько раз шарик выпадает на черное после сотен случайных бросков. В настоящее время метод Монте-Карло является ключевым инструментом во многих областях науки. Но когда в Лос-Аламосе у Станислава Улама появлялось свободное время, он отдыхал, изобретая игры с одним участником, основанные на создании шаблонов из ячеек решетки. Изменение правил создания таких шаблонов позволяло строить фигуры, которые могли разрастаться и меняться весьма необычными способами.

Спирали Улама: числа от 1 до 100 (вверху) и от 1 до 65 000 (внизу)

Улам и фон Нейман были близкими друзьями, эмигрантами из Восточной Европы, выходцами из верхушки среднего класса с еврейскими корнями. Оба очутились в одинаковой политической ситуации, и оба обладали выдающимся интеллектом. Фон Неймана принято считать математиком, оказавшим заметное влияние на формирование облика современного мира: он один из создателей компьютеров, ядерной бомбы и теории игр (математики принятия решений). Личностные качества фон Неймана соответствовали его математическим достижениям. В Принстоне он славился как устроитель крупных вечеринок, во время которых часто удалялся в свой кабинет, потому что любил работать под шум таких гуляний.

Фон Нейман был очарован и одновременно напуган потенциальными последствиями, которые могли повлечь за собой создаваемые им машины. В период, наступивший после Второй мировой войны, в фантастических романах и голливудских фильмах изображалось будущее, где роботы захватили мир. Фон Нейман хотел выяснить, что понадобится машине, чтобы воспроизвести себя. Он провел мысленный эксперимент с участием плавающего в озере робота с глазом и механической рукой, умеющей брать необходимые комплектующие и строить новую версию себя. Однако этот эксперимент застопорился из-за механических осложнений. Улам выдвинул предположение, что, для того чтобы сосредоточиться исключительно на логических аспектах самовоспроизведения, вместо работы с реальной машиной фон Нейману следует проанализировать фигуры, образующиеся на решетке ячеек, как в пасьянсах, которые он раскладывал в Лос-Аламосе. В процессе обсуждения этой задачи двое ученых изобрели новую математическую концепцию — «клеточный автомат». По сути, это разграфленная на клетки поверхность, в которой поведение каждой клетки зависит только от состояния соседних клеток. Фон Нейман разработал клеточный автомат, в котором каждая клетка находилась в одном из 29 состояний, и придумал правила, призванные обеспечить самовоспроизведение исходного шаблона, состоящего из 200 000 клеток. Клеточные автоматы не привлекали к себе особого академического интереса до тех пор, пока на них не обратил внимание британский математик с еще более игривым разумом, чем у Улама.

В 1960-х годах комната отдыха математического факультета Кембриджского университета напоминала группу продленного дня в школе. Преподаватели и студенты постоянно играли там в настольные игры и придумывали новые. Идей было так много, что один преподаватель даже вел файл под названием Games Without Names («Игры без названий») и сопутствующий файл — Names Without Games («Названия без игр»). В этой среде процветал Джон Конвей, ливерпульский фанатик игры в нарды и восходящая звезда математики. Одним из изобретений Конвея был клеточный автомат на квадратной сетке, которому он дал имя Game of Life («Игра “Жизнь”»). Однако слово «игра» не совсем соответствовало его сути, поскольку там не было победителей, проигравших и даже игроков. Игра «Жизнь» представляла собой двумерную вселенную, подчиняющуюся четырем законам. Смысл игры состоял в том, чтобы построить исходную конфигурацию, или первоначальный шаблон, а затем наблюдать за тем, как он эволюционирует.

В игре «Жизнь» клетка является либо живой, либо мертвой и подчиняется следующим правилам.

Рождение: мертвая клетка, имеющая ровно три живые соседние клетки, становится живой.

Выживание: живая клетка, имеющая две или три живые соседние клетки, продолжает жить.

Смерть от одиночества: живая клетка, у которой нет по соседству живых клеток или есть только одна такая клетка, умирает.

Смерть от перенаселенности: живая клетка с четырьмя или более соседними клетками умирает.

Примечание. У каждой клетки есть восемь соседей; к их числу относятся четыре смежные клетки и четыре клетки, с которыми она соприкасается по диагоналям в углах. Перечисленные выше законы применяются по отношению ко всем клеткам одновременно, и каждый раз, когда это происходит, появляется новое поколение клеток.

Вот и все. Больше в игре «Жизнь» делать нечего.

Конвей сформулировал правила рождения, смерти и выживания таким образом, чтобы шаблоны не погибали и не эволюционировали слишком быстро, но чтобы их поведение было как можно интереснее. Представьте себе одну живую клетку. Она умирает от одиночества в следующем поколении. Точно так же шаблон, состоящий из двух соседних клеток, погибает после смены поколения. Однако, когда мы начнем рассматривать фигуры, состоящие из трех живых клеток, эти организмы окажутся достаточно жизнеспособными, чтобы выжить — во всяком случае, на какое-то время. На представленном ниже рисунке показано, что происходит с конфигурацией клеток в виде шеврона, состоящей из трех живых клеток. (Живые клетки черные, мертвые — белые.) У двух живых клеток в основании шеврона есть только по одной живой соседней клетке, а значит, они умрут, когда мы применим к ним перечисленные выше законы. У живой клетки на вершине есть две живые соседние клетки, поэтому она выживает, а у мертвой клетки посредине три живые клетки по соседству, поэтому она становится живой. То есть в следующем поколении шеврон превращается в столбец из двух живых клеток, а еще в одном погибает.

Как эволюционирует шеврон

Судьба еще четырех исходных конфигураций из трех клеток (триплетов) показана на рисунке ниже. (На этом рисунке каждое новое поколение отображается ниже предыдущего. В действительности каждое новое поколение занимает те же клетки.) Ко второму поколению два триплета погибают. Однако квадрат из четырех клеток, который Конвей назвал «блоком», продолжает жить, оставаясь в неизменном виде во всех последующих поколениях. Конфигурация из выстроившихся в линию трех клеток, расположенная то вертикально, то горизонтально, известна как «мигалка». Фигуры, которые не меняются (подобные блоку) или находятся то в одном, то в другом фиксированном состоянии, называются устойчивыми конфигурациями.

Судьба триплетов

Как эволюционирует шеврон

Настоящее волшебство мы увидим при анализе эволюции пяти тетрамино (фигур, положенных в основу компьютерной игры «Тетрис»), состоящих из четырех живых клеток, примыкающих друг к другу. Блок, как мы уже заметили, остается в неизменном состоянии. Четыре другие фигуры представлены на рисунке ниже. Тетрамино в форме букв I и S превращаются через два поколения в устойчивую конфигурацию, получившую название «улей», а L-образное тетрамино трансформируется в улей через три поколения. С другой стороны, тетрамино в форме буквы T обладает взрывной энергией и через девять поколений эволюционирует в окончательную конфигурацию, состоящую из четырех мигалок, — «светофор».

Судьба тетрамино

Самой увлекательной особенностью игры «Жизнь» была ее непредсказуемость. Не было другого способа узнать, что произойдет даже с самыми простыми фигурами, кроме отслеживания их жизни на протяжении многих поколений, что Конвей и его коллеги делали вручную. Живые клетки были фишками, которые размещались на доске для игры го с разметкой 19 × 19 линий. Когда для шаблона требовалось больше места, на полу укладывали дополнительные доски. Были найдены новые устойчивые конфигурации, получившие такие названия, как «батон», «корабль», «лодка» и «змея». Иногда исходный шаблон погибал или быстро менялся, превращаясь в одну из известных устойчивых конфигураций, а иногда начинал жить своей жизнью, что приводило всех в сильное волнение. Например, пентамино в форме буквы R состояло всего из пяти клеток, но продолжало эволюционировать на протяжении десятков поколений, пока на 69-м поколении не произошло исключительное событие. Эта конфигурация произвела на свет фигуру из пяти клеток, скользившую по доске.

Новая фигура получила имя «глайдер» (ее поведение проиллюстрировано на рисунке ниже). Через два поколения конфигурация переворачивается на другую сторону, а еще через два снова поворачивается таким образом, что оказывается на одну клетку ниже и на одну дальше от исходной позиции. Глайдер продолжает смещаться на одну клетку вниз и одну вперед каждые четыре поколения. Он будет двигаться в одном и том же направлении по диагонали до бесконечности, если ничто не преградит ему путь. «Главный систематик» Конвей выделил в игре «Жизнь» новый вид фигур, подобных глайдеру, которые перемещаются по прямым линиям, и назвал их космическими кораблями.

Глайдер

В 1970 году журналист Мартин Гарднер написал об игре «Жизнь» в своей многолетней рубрике в журнале Scientific American, что способствовало превращению математической игры Конвея в одно из первых компьютерных увлечений, охвативших весь мир. Отслеживание эволюции фигур в игре «Жизнь» на доске для го требовало больших временных затрат и не было защищено от ошибок. Компьютеры позволяли отслеживать конфигурации гораздо дольше; кроме того, когда сменяющие друг друга поколения клеток мелькали на экране, фигуры как будто оживали. Решетка с разбросанными по ней живыми клетками представляла собой первичную среду обитания изменчивых, постоянно преобразующихся конфигураций. Например, R-образное пентамино искрилось и пенилось на протяжении целых 1103 поколений, оставляя после себя обломки в виде корабля, лодки, батона, четырех ульев, четырех мигалок, шести глайдеров и восьми блоков. Запрограммировать игру «Жизнь» не составляло труда, поскольку в ней было всего четыре правила; тем не менее эта игра демонстрировала слишком сложное поведение, и его еще не удавалось добиться на компьютерах. Создание шаблонов и наблюдение за их дальнейшей жизнью вызывали такую зависимость, что, по оценкам Гарднера, это обошлось американской экономике в миллионы долларов компьютерного времени. Один читатель рассказал Гарднеру, что установил под своим рабочим столом секретную кнопку, для того чтобы переключать компьютер на игру «Жизнь», когда коллеги выходят из кабинета.

В Массачусетском технологическом институте (МТИ) игра «Жизнь» стала образом жизни. Одна сплоченная группа склонных к анархии и веселью, но очень умных студентов поставила перед собой цель изучить эту игрушечную вселенную глубже, чем кто-либо другой. Это были первые компьютерные хакеры, настоящие техногики. Общинная, антиавторитарная позиция хакеров оказала огромное влияние на формирование зарождающейся компьютерной культуры Америки, задавая тон новаторам более позднего периода, таким как Стив Джобс и Билл Гейтс. «План состоял в том, чтобы просто собрать всю эту дичь и одомашнить ее», — объяснил Билл Госпер, король хакеров, который преподает сейчас математику в Лос-Альтосе. Госпер проводил целые ночи в компьютерном зале MIT, играя в «Жизнь», и так продолжалось почти два года.

Конвей опубликовал на страницах журнала Scientific American задачу и предложил за ее решение приз в размере 50 долларов. Существует ли конфигурация, которая продолжает расти и у которой общее количество живых клеток увеличивается бесконечно? Госпер нашел такую конфигурацию и получил приз. «Глайдерное ружье» — это фигура из 36 живых клеток, пульсирующая как бьющееся сердце, порождая новый глайдер через каждые 30 поколений. Эти глайдеры один за другим отдаляются от исходной фигуры по диагонали, подобно бесконечному потоку пуль, выстреливаемых из ружья. Открытие глайдерного ружья сместило фокус изучения игры «Жизнь» с зоологии на физику. Госпер и его друзья-натуралисты больше не занимались пассивным исследованием флоры и фауны, переключившись на баллистику и изобретение фигур, в состав которых входят глайдерные ружья, стреляющие в другие фигуры. Можно было выстрелить двумя глайдерами друг в друга таким образом, что оба исчезали, не оставив после себя никаких обломков, как будто каким-то волшебным образом растворяясь в воздухе. «Мы пытались найти способ создавать что-то новое, сталкивая глайдеры между собой и наблюдая, что из этого выйдет, — объяснял Госпер. — А затем возникал другой вопрос: что произойдет, если ударить глайдерами по фигурам, полученным в результате столкновения глайдеров?» В ходе поиска ответа на этот вопрос Госпер открыл новую устойчивую конфигурацию из семи клеток под названием «пожиратель». Когда глайдер сталкивается с пожирателем, первый исчезает, а второй восстанавливается до исходного состояния, что создает впечатление, будто он поглотил глайдер. Кроме того, пожиратель поглощает другие устойчивые фигуры, расположенные рядом с ним, всегда восстанавливаясь после первоначального взаимодействия.

Пожиратель был первым признаком того, что игре «Жизнь» можно найти применение в реальном мире, например в проектировании объектов, которые способны к самовосстановлению. Нельзя сказать, что Госпера интересовало именно это. Для него было важно то, что глайдерное ружье и пожиратель позволяют вывести игру «Жизнь» на новый уровень — уровень разработки больших проектов, в рамках которых огромные конфигурации можно было бы создавать из сотен глайдеров, скачущих между разными элементами, а пожирателей разместить таким образом, чтобы они подбирали ненужные обломки. Первой конфигурацией подобного типа, которую Госперу удалось составить, был так называемый размножитель — фигура, порождающая глайдеры. Он начинает где-то с 50 глайдеров и ускоряет их воспроизведение так быстро, что примерно на 6500-м поколении количество глайдеров превышает количество поколений.

По мере увеличения банка знаний любители игры «Жизнь» выстраивали все более удивительные конфигурации. Одна из моих любимых представляет собой имитацию решета Эратосфена — метода поиска простых чисел, используемого древними греками. Решето, смоделированное в игре «Жизнь», состоит в основном из ружей, глайдеров и пожирателей. Его исходная конфигурация включает 5169 живых клеток. Основной элемент решета — ружье, выстреливающее фигуру из 9 клеток под названием «легкий космический корабль» в горизонтальном направлении, через равные промежутки времени. Глайдеры обстреливают космические корабли, из которых выживают только второй, третий, пятый, седьмой, одиннадцатый и т. д. — другими словами, корабли, порядковый номер которых — простое число. (Подробное разъяснение того, как это работает, можно найти в Приложении 8.)

Мне нравится решето, смоделированное в игре «Жизнь», поскольку из древнегреческого математического инструмента оно превратилось в межгалактическую перестрелку между флотилиями глайдеров и космических кораблей. Наблюдать за данной конфигурацией — это как будто смотреть батальную сцену в фантастической эпопее или, возможно, отслеживать эволюцию колонии муравьев, поведение которых носит сугубо математический характер. Не забывайте: как только вы построите исходную конфигурацию, вам не нужно вмешиваться в дальнейший процесс. Эта фигура может продолжать свою жизнь до бесконечности, отстреливая космические корабли и оставляя в живых лишь те из них, порядковый номер которых представляет собой простое число.

«Уровень мастерства реально поражает, — сказал Госпер о самых лучших конфигурациях. — Люди, которые пытаются [создавать фигуры], быстро осознают, насколько это сложно, а удачные образцы приводят их в неописуемый восторг. Для того чтобы сосредоточиться на игре в достаточной степени, нужно находиться почти в состоянии невменяемости». За период с семидесятых годов до наших дней построены сотни удивительных конфигураций, в том числе и вычисляющая значение числа π, которую изобрел британский подросток по имени Адам Гаучер. К чему еще стремиться? «Жизнь — неистощимый источник вопросов и задач», — резюмировал Госпер.

Игра «Жизнь» подвергает сомнению наши предвзятые представления о том, как работает этот мир, поскольку она показывает, как простой набор локальных правил может генерировать невероятно сложное общее поведение. При взгляде на такую идеально интегрированную систему, как решето Эратосфена, удивляет то, что каждая клетка взаимодействует всего с восемью соседними клетками.

Игра «Жизнь» демонстрирует также существование разных реальностей на разных уровнях игры. Решето Эратосфена — это конфигурация, разработанная на основе физических свойств глайдерных ружей с использованием технологии столкновений и космических кораблей. Однако на более детальном уровне таких вещей, как «столкновение» или «космический корабль», нет. Есть лишь неподвижные клетки, которые могут быть либо «живыми», либо «мертвыми».

По мере создания все более сложных фигур возникает вопрос: каков предел того, что может сделать конфигурация в игре «Жизнь»? Да буквально все, на что способен ваш ПК, планшет или смартфон. Если задача выполнима с помощью компьютера, тогда это можно сделать и посредством конфигурации в игре «Жизнь».

Конвей доказал истинность этого утверждения, продемонстрировав, что можно создать компьютер «Жизни», другими словами — исходную конфигурацию живых клеток, имитирующую внутреннюю схему компьютера. Вам придется поверить мне на слово (или прочитать книгу по информатике), но внутренняя схема компьютера на базовом уровне состоит из следующих компонентов: проводники, логические элементы и регистр памяти. Генератор тактовых импульсов порождает электронные импульсы, представляющие двоичные числа. Наличие импульса — это 1, а его отсутствие — 0. Конвей понял, что глайдеры могут выполнять функции импульсов, передающихся по проводникам. Следовательно, поток глайдеров может представить любое число, состоящее из нолей и единиц, как показано на рисунке ниже. Поскольку глайдеры двигаются по диагонали, я разместил сетку под углом 45 градусов.

Поток глайдеров

Конвей разработал логический элемент простейшего типа, выполняющий операцию НЕ (операцию отрицания). Логический элемент — это устройство, имеющее несколько входов и выходов. У логического элемента, выполняющего операцию НЕ, только один вход и один выход. Сигнал на выходе противоположен сигналу на входе: он меняется с 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 клеток. Крупные конфигурации состоят в основном из пустого пространства. «Возможно, в игре “Жизнь” так много пустого пространства по той же причине, почему его так много в нашем мире, — пояснил Пол. — У атомов должно быть достаточно места для того, чтобы они выполняли свою работу».

Появление «Джемини» усилило ожидания в отношении следующего этапа исследования игры «Жизнь». Если исходная конфигурация порождает копии, в которых есть небольшие отличия от оригинала, это может обусловить дарвиновский естественный отбор. В 1982 году Джон Конвей выдвинул предположение о том, что если бы решетка игры «Жизнь» была достаточно большой и в исходном состоянии клетки располагались на ней в случайном порядке, то «через приличный промежуток времени появились бы разумные существа, способные к воспроизводству». Три десятилетия спустя эта гипотеза Конвея по-прежнему будоражит кровь любителям игры «Жизнь». Самую интересную работу выполняет Ник Готтс, специалист по комплексным системам из Абердина (Шотландия), который ищет новые конфигурации, заполняя сетку игры «Жизнь» живыми клетками в произвольном порядке. Он называет свой проект «рассеянной Жизнью», поскольку относительная доля живых клеток должна быть довольно низкой по сравнению с количеством мертвых клеток, иначе это приведет к слишком большому числу неконтролируемых взаимодействий. «В некоторых конфигурациях присутствует нечто, напоминающее естественный отбор, — объясняет Ник. — Есть конфигурации, регулирующие появление других конфигураций аналогичного типа. Я убежден, что, если бы моя программа выполнялась достаточно долго, вступил бы в действие закон естественного отбора».

Клеточные автоматы с более простой структурой, чем игра «Жизнь», могут демонстрировать столь же сложное поведение. Рассмотрим в качестве примера одномерный клеточный автомат: ряд клеток, в котором каждая клетка имеет только двух соседей. Кроме того, каждая клетка может быть либо живой, либо мертвой.

Возьмем следующее правило:

Если оба соседа клетки пребывают в том же состоянии, что и она сама, то клетка умирает в следующем поколении. В противном случае в следующем поколении она остается живой.

Это правило проиллюстрировано ниже. На рисунке показаны восемь возможных комбинаций клетки и двух ее соседей. Под каждой комбинацией изображено состояние клетки после смены поколения. В первой комбинации живая клетка находится в окружении двух живых соседних клеток. Значит, в следующем поколении она умрет. Вторая комбинация содержит живую клетку слева и мертвую справа, стало быть, средняя клетка останется в следующем поколении в живых. Если две соседние клетки одинакового цвета, внизу будет получена белая клетка. Если разного, нижняя клетка будет черной.

Чтобы понять суть этого правила, представьте себе группу людей, стоящих каждое утро в очереди на автобусной остановке, причем в одном и том же порядке. У каждого человека два соседа, по одному с каждой стороны. Пусть наше правило касается шляп: если оба ваши соседа носят шляпу, то шляпы — это слишком типичное явление, поэтому на следующий день вы шляпу не наденете. Если ни у одного из соседей шляпы нет, значит, они не в моде, поэтому на следующий день вы тоже шляпу не наденете. Однако если шляпу носит только один ваш сосед, то она еще не вышла из моды и не говорит о плохом вкусе. Данный клеточный автомат представляет собой модель изменения ежедневных предпочтений в ношении головных уборов.

Для того чтобы проиллюстрировать поведение одномерного клеточного автомата, давайте нарисуем ряд с одной живой клеткой (поколение 0), а затем применим указанное выше правило к каждой клетке для создания нового ряда, расположенного ниже (поколение 1). Затем применим это правило к каждой клетке данного ряда, чтобы получить следующий новый ряд (поколение 2), и т. д. На представленном рисунке показано, что при этом произойдет. (Обратите внимание, что вершина треугольника — это живая клетка первого ряда, а каждый новый ряд — следующее поколение, в отличие от игры «Жизнь», где вся сетка образует одно поколение. Я опустил на рисунке саму сетку, чтобы полученная конфигурация была видна более четко.) В итоге мы получим прекрасный математический зиккурат, известный как «треугольник Серпинского», — фрактальную структуру, состоящую из вложенных треугольников.

Существует 8 комбинаций клетки и ее соседей, а также два возможных состояния (живая или мертвая клетка), а значит, есть 28 = 256 разных наборов «генетических правил» для одномерных клеточных автоматов. Эти правила пронумерованы от 1 до 256. На представленном выше рисунке показано правило 90, порождающее упорядоченные фигуры. Другие правила, такие как правило 30, более причудливы. Это правило, а также конфигурация, которую оно порождает, начиная с одной живой клетки, проиллюстрировано на рисунке ниже. Данная конфигурация представляет собой совокупность упорядоченных и хаотичных фрагментов. Зигзагообразная корка на левой боковой поверхности демонстрирует упорядоченность. Однако по мере передвижения направо мы видим неупорядоченную бугристую поверхность, состоящую из треугольников самых разных форм и размеров.

На визитных карточках Стивена Вольфрама изображен рисунок фигуры, которую порождает правило 30. Когда я встретился с ним, он вынул такую визитку из бумажника и дал мне. Мы расположились в главном офисе его компании Wolfram Research, находящемся в городе Шампейн. У Вольфрама лицо обладающего необыкновенными математическими способностями ребенка, достигшего средних лет: круглое и бледное, с хохолками волос вокруг типичной профессорской макушки. Во время разговора он пристально всматривался куда-то, думая о чем-то своем, а его глаза за стеклами очков мерцали, подобно электронному дисплею, демонстрируя неустанную работу мозга. Вольфрам рано начал научную карьеру, опубликовав свою первую исследовательскую работу еще во время учебы в Итоне в 1970-х. Когда ему исполнилось немногим более двадцати лет, он уже работал в Институте перспективных исследований в Принстоне. Став одним из первых новообращенных в компьютерную веру, он разработал язык программирования, который лег в основу системы компьютерной алгебры Mathematica — пакета программ, позволяющих чертить кривые и решать уравнения. В настоящее время она широко используется в сфере образования и разных отраслях экономики. С 1987 года Вольфрам возглавляет компанию Wolfram Research, которая благодаря успеху системы Mathematica дала ему возможность проводить собственные научные исследования независимо от университетов.

Правило 30: его генетические законы, его эволюция после 50 поколений и эволюция после более 200 поколений

Вольфрам первым в восьмидесятых годах достаточно глубоко изучил одномерные клеточные автоматы; нумерация правил от 1 до 256 берет свое начало именно в его работе. Когда Вольфрам увидел правило 30, это было подобно удару молнии в его научной интуиции. «Это самое удивительное, с чем я когда-либо встречался в науке», — сказал он. Вольфрам был поражен тем, что такое простое правило способно сгенерировать столь сложную конфигурацию. Он внимательно проанализировал колонку, расположенную под исходной живой клеткой в первом ряду. Если взять за основу то, что живая клетка — это 1, а мертвая — 0, то эта колонка состояла из таких клеток: 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0… В этом не было никакой закономерности. К большому удивлению Вольфрама, стандартные статистические тесты показали, что это абсолютно произвольная последовательность. Правило 30 полностью детерминировано, однако конфигурация ячеек в центральном столбце настолько непредсказуема, что ее невозможно отличить от последовательного подбрасывания монеты. (Вольфрам запатентовал правило 30 как генератор случайных чисел и применил его в системе Mathematica.)

Внимание Вольфрама привлекло еще одно правило — правило 110. Оно формировало сетку ячеек, которая тоже представляла собой совокупность регулярных и случайных фигур. Вольфрам предположил, что данного уровня сложности достаточно для такой же имитации работы компьютера, на которую способна игра «Жизнь». В 2004 году Мэтью Кук доказал истинность предположения Вольфрама. Следовательно, теоретически единственный ряд клеток может сделать все, что и компьютер, используя всего один набор правил, определяющих, является ли клетка живой или мертвой, только на основании информации о состоянии двух ее соседей. Точно так же один ряд людей может сделать все, на что способен компьютер, воспользовавшись всего одним набором правил, определяющих, следует ли надевать шляпу или нет.

Клеточные автоматы — это дискретные математические модели, в которых фиксированные локальные правила генерируют неожиданно сложное поведение в более крупном масштабе. Вольфрам — один из главных сторонников той точки зрения, что клеточные автоматы — не только увлекательная математическая игра, но и способ объяснить сложность физического мира. Мысли Вольфрама по этому поводу изложены в книге A New Kind of Science («Новый вид науки»), которую он опубликовал за свой счет в 2002 году. В частности, в ней Вольфрам утверждает, что информация, полученная благодаря анализу правила 30, открывает новую научную парадигму. Возьмем в качестве примера раковину ядовитой парчовой улитки, изображенную на рисунке ниже. Общепринятое представление об эволюции объясняет такой рисунок как результат естественного отбора. Но посмотрите на иллюстрацию правила 30! «Я считаю, что это просто удивительно, — говорит Вольфрам. — Достаточно всего лишь наугад выбрать эти простые [правила клеточных автоматов] — и вы получите нечто подобное [рисунку на этой раковине]».

Раковина парчовой улитки, или текстильного конуса

© iStock.com/busypix

Однако Вольфрам на этом не останавливается, поскольку убежден, что на базовом уровне Вселенная представляет собой клеточный автомат. Другими словами, он считает, что структура Вселенной аналогична решетке в игре «Жизнь», но существует вне пространства и времени. Следовательно, то, что происходит с вами сейчас, когда вы читаете эту книгу, — это энное поколение исходной конфигурации клеток, прошедших процесс эволюции в соответствии с небольшим набором локальных правил. Вольфрам поставил перед собой цель найти эти правила. «Если окажется, что они сводятся к трем строкам программы, а мы так и не начнем искать их в текущем столетии, это будет весьма досадно», — сетует он.

Вольфрам — не единственный ученый, который считает, что Вселенная может быть клеточным автоматом, но только он потратил массу времени и денег на попытки это доказать. Он систематически проводит испытания разных наборов правил, для того чтобы увидеть, какие вселенные они порождают. «Какое-то время у меня получалось нечто столь оригинальное, что я смог сказать: компьютер у меня в подвале ведет поиски Вселенной».

Вольфрам так описал свою стратегию: «Когда анализируешь разные наборы очень простых правил, становится очевидным, что некоторые из них безнадежны. Как будто вселенная погибает через два шага или же бесконечно расширяется таким образом, что ни один ее участок не имеет никакой связи с любым другим участком той же вселенной. Все это своего рода патология. И ты продолжаешь одолевать эти вселенные, а когда добираешься до тысячной, начинаешь находить такие, одолеть которые не так уж легко». Вольфрам добавил, что он находил вселенные, в чьем отношении «не было очевидно, что это не наша Вселенная», но отвлекался на выполнение задач, связанных с управлением компанией, и на другие проекты. Тем не менее он планирует возобновить охоту на вселенные в будущем. «Я надеюсь, что однажды на обороте моей визитной карточки будут написаны законы Вселенной, — смеется он. — Вот это была бы неплохая бизнес-услуга».

Является ли Вселенная клеточным автоматом или нет, но эта концепция все чаще используется в науке для моделирования самых разных феноменов, таких как транспортный поток, разрастание ряски на озере и рост городов. При этом в роли клетки может выступать отрезок дороги, фрагмент озера или участок земли. Существует еще одна область применения таких одномерных клеточных автоматов, ее открыл Крейг Лент из Университета Нотр-Дам, — квантово-точечные клеточные автоматы, в которых крохотные «квантовые точки» меняют свой электрический заряд исходя из конфигурации соседних точек. Лент надеется, что со временем эта нанотехнология займет место транзистора, поскольку транзистор, сделанный из квантовых точек, будет иметь гораздо меньшие размеры и выделять меньше тепла, чем обычный транзистор. Если квантово-точечная технология будет успешно разработана, то однажды клеточный автомат может появиться во всех электронных устройствах.

Джон фон Нейман и Станислав Улам разработали клеточный автомат для решения задачи, возникшей под влиянием реального мира: что понадобится машине для того, чтобы построить точную копию самой себя. От перспективы будущего, в котором есть самовоспроизводящиеся машины, кровь стынет в жилах. Однако Джон Конвей подхватил эту идею и превратил в причудливое и захватывающее математическое развлечение. Впоследствии идея клеточных автоматов была переосмыслена и нашла применение, не связанное с самовоспроизведением. Это хорошо знакомый процесс: математики живут задачами, существующими в реальном мире; играют с различными концепциями ради удовольствия, а затем для этих концепций (может, годы, столетия или даже тысячелетия спустя) обнаруживаются новые области применения. Дальнейшее развитие технологий невозможно без свежих математических идей, а наука обретает все большую способность объяснить суть того мира, в котором мы живем. В начале книги я говорил, что математика сродни шутке. Я хотел бы изменить эту формулировку. Математика — это игра и всегда ею была.

Математика — это игра жизни.