Решето Эратосфена
Это очень красивая и наглядная решетка, так как она сразу же говорит вам, что все простые числа должны находиться в первом и пятом рядах, а значит, они все либо на единицу больше, либо на единицу меньше числа, кратного 6. Однако самый важный момент, на который необходимо обратить внимание, — это причина, вынуждающая нас отсеивать числа: простые числа не появляются в каком-либо предсказуемом порядке. Если бы мы продолжили строить эту решетку до бесконечности, они были бы разбросаны в случайном порядке по первому и пятому рядам. Тот факт, что простые числа настолько легко найти, но их распределение столь непредсказуемо, — одна из самых ранних и наиболее непостижимых неожиданностей в математике.
В 1963 году 54-летний Станислав Улам отвлекся от лекции, на которой присутствовал, и принялся машинально чертить что-то на листе бумаги. Он нарисовал сетку из горизонтальных и вертикальных линий и стал нумеровать образованные путем их пересечения клетки, начав с единицы в центре и двигаясь по спирали. Наверное, ему было действительно скучно, потому что после этого он отметил все простые числа кружочками. Мы знаем, что простые числа не подчиняются очевидной закономерности, так что такого там увидел Улам? Как ни странно, он заметил нечто весьма неожиданное. Простые числа выстраивались вдоль диагональных линий (см. рисунок ниже), создавая рисунок, известный сегодня как спираль Улама. Когда Улам запрограммировал компьютер на построение такой спирали от 1 до 65 000, там тоже образовались диагонали, а также горизонтальные и вертикальные теневые области. Спираль Улама позволяет сделать волнующее предположение о том, что за беспорядочным шумом можно обнаружить музыку.
Улам был одним из польских математиков, которые в 1930-х годах во Львове принимали участие в создании «Шотландской книги». В 1935 году Джон фон Нейман, математик венгерского происхождения из Института перспективных исследований в Принстоне, пригласил Улама в США, куда тот и переехал навсегда в 1939 году. Четыре года спустя фон Нейман сделал Уламу, работавшему тогда в Висконсинском университете, более интригующее предложение: перебраться в Нью-Мексико и присоединиться к нему в работе над неизвестным проектом. Улам взял в университетской библиотеке путеводитель по штату Нью-Мексико и увидел, что до него путеводитель брали его коллеги, которые исчезли куда-то без всяких объяснений. Выяснив, в каких областях они работали, он понял, что именно его просят сделать.
Так Улам присоединился к Манхэттенскому проекту в Лос-Аламосе, где сыграл ключевую роль в разработке термоядерного оружия, а также создал новый раздел математики. Он понял, что если поведение физической системы является слишком сложным, то для того, чтобы его прогнозировать, нужно предоставить компьютеру возможность сделать множество случайных оценок, а затем получить более точные показатели с помощью статистических методов. Во время одной из поездок на автомобиле Улам объяснил этот метод фон Нейману; тогда и было придумано для него название — «метод Монте-Карло». Например, для того чтобы определить вероятность того, что шарик рулетки остановится на черном, игроку не нужно решать уравнение — он может просто подсчитать, сколько раз шарик выпадает на черное после сотен случайных бросков. В настоящее время метод Монте-Карло является ключевым инструментом во многих областях науки. Но когда в Лос-Аламосе у Станислава Улама появлялось свободное время, он отдыхал, изобретая игры с одним участником, основанные на создании шаблонов из ячеек решетки. Изменение правил создания таких шаблонов позволяло строить фигуры, которые могли разрастаться и меняться весьма необычными способами.
Спирали Улама: числа от 1 до 100 (вверху) и от 1 до 65 000 (внизу)
Улам и фон Нейман были близкими друзьями, эмигрантами из Восточной Европы, выходцами из верхушки среднего класса с еврейскими корнями. Оба очутились в одинаковой политической ситуации, и оба обладали выдающимся интеллектом. Фон Неймана принято считать математиком, оказавшим заметное влияние на формирование облика современного мира: он один из создателей компьютеров, ядерной бомбы и теории игр (математики принятия решений). Личностные качества фон Неймана соответствовали его математическим достижениям. В Принстоне он славился как устроитель крупных вечеринок, во время которых часто удалялся в свой кабинет, потому что любил работать под шум таких гуляний.
Фон Нейман был очарован и одновременно напуган потенциальными последствиями, которые могли повлечь за собой создаваемые им машины. В период, наступивший после Второй мировой войны, в фантастических романах и голливудских фильмах изображалось будущее, где роботы захватили мир. Фон Нейман хотел выяснить, что понадобится машине, чтобы воспроизвести себя. Он провел мысленный эксперимент с участием плавающего в озере робота с глазом и механической рукой, умеющей брать необходимые комплектующие и строить новую версию себя. Однако этот эксперимент застопорился из-за механических осложнений. Улам выдвинул предположение, что, для того чтобы сосредоточиться исключительно на логических аспектах самовоспроизведения, вместо работы с реальной машиной фон Нейману следует проанализировать фигуры, образующиеся на решетке ячеек, как в пасьянсах, которые он раскладывал в Лос-Аламосе. В процессе обсуждения этой задачи двое ученых изобрели новую математическую концепцию — «клеточный автомат». По сути, это разграфленная на клетки поверхность, в которой поведение каждой клетки зависит только от состояния соседних клеток. Фон Нейман разработал клеточный автомат, в котором каждая клетка находилась в одном из 29 состояний, и придумал правила, призванные обеспечить самовоспроизведение исходного шаблона, состоящего из 200 000 клеток. Клеточные автоматы не привлекали к себе особого академического интереса до тех пор, пока на них не обратил внимание британский математик с еще более игривым разумом, чем у Улама.
В 1960-х годах комната отдыха математического факультета Кембриджского университета напоминала группу продленного дня в школе. Преподаватели и студенты постоянно играли там в настольные игры и придумывали новые. Идей было так много, что один преподаватель даже вел файл под названием Games Without Names («Игры без названий») и сопутствующий файл — Names Without Games («Названия без игр») [2]. В этой среде процветал Джон Конвей, ливерпульский фанатик игры в нарды и восходящая звезда математики. Одним из изобретений Конвея был клеточный автомат на квадратной сетке, которому он дал имя Game of Life («Игра “Жизнь”»). Однако слово «игра» не совсем соответствовало его сути, поскольку там не было победителей, проигравших и даже игроков. Игра «Жизнь» представляла собой двумерную вселенную, подчиняющуюся четырем законам. Смысл игры состоял в том, чтобы построить исходную конфигурацию, или первоначальный шаблон, а затем наблюдать за тем, как он эволюционирует.
В игре «Жизнь» клетка является либо живой, либо мертвой и подчиняется следующим правилам.
Рождение: мертвая клетка, имеющая ровно три живые соседние клетки, становится живой.
Выживание: живая клетка, имеющая две или три живые соседние клетки, продолжает жить.
Смерть от одиночества: живая клетка, у которой нет по соседству живых клеток или есть только одна такая клетка, умирает.
Смерть от перенаселенности: живая клетка с четырьмя или более соседними клетками умирает.
Примечание. У каждой клетки есть восемь соседей; к их числу относятся четыре смежные клетки и четыре клетки, с которыми она соприкасается по диагоналям в углах. Перечисленные выше законы применяются по отношению ко всем клеткам одновременно, и каждый раз, когда это происходит, появляется новое поколение клеток.
Вот и все. Больше в игре «Жизнь» делать нечего.
Конвей сформулировал правила рождения, смерти и выживания таким образом, чтобы шаблоны не погибали и не эволюционировали слишком быстро, но чтобы их поведение было как можно интереснее. Представьте себе одну живую клетку. Она умирает от одиночества в следующем поколении. Точно так же шаблон, состоящий из двух соседних клеток, погибает после смены поколения. Однако, когда мы начнем рассматривать фигуры, состоящие из трех живых клеток, эти организмы окажутся достаточно жизнеспособными, чтобы выжить — во всяком случае, на какое-то время. На представленном ниже рисунке показано, что происходит с конфигурацией клеток в виде шеврона, состоящей из трех живых клеток. (Живые клетки черные, мертвые — белые.) У двух живых клеток в основании шеврона есть только по одной живой соседней клетке, а значит, они умрут, когда мы применим к ним перечисленные выше законы. У живой клетки на вершине есть две живые соседние клетки, поэтому она выживает, а у мертвой клетки посредине три живые клетки по соседству, поэтому она становится живой. То есть в следующем поколении шеврон превращается в столбец из двух живых клеток, а еще в одном погибает.
Как эволюционирует шеврон
Судьба еще четырех исходных конфигураций из трех клеток (триплетов) показана на рисунке ниже. (На этом рисунке каждое новое поколение отображается ниже предыдущего. В действительности каждое новое поколение занимает те же клетки.) Ко второму поколению два триплета погибают. Однако квадрат из четырех клеток, который Конвей назвал «блоком», продолжает жить, оставаясь в неизменном виде во всех последующих поколениях. Конфигурация из выстроившихся в линию трех клеток, расположенная то вертикально, то горизонтально, известна как «мигалка». Фигуры, которые не меняются (подобные блоку) или находятся то в одном, то в другом фиксированном состоянии, называются устойчивыми конфигурациями.
Судьба триплетов
Как эволюционирует шеврон
Настоящее волшебство мы увидим при анализе эволюции пяти тетрамино (фигур, положенных в основу компьютерной игры «Тетрис»), состоящих из четырех живых клеток, примыкающих друг к другу. Блок, как мы уже заметили, остается в неизменном состоянии. Четыре другие фигуры представлены на рисунке ниже. Тетрамино в форме букв I и S превращаются через два поколения в устойчивую конфигурацию, получившую название «улей», а L-образное тетрамино трансформируется в улей через три поколения. С другой стороны, тетрамино в форме буквы T обладает взрывной энергией и через девять поколений эволюционирует в окончательную конфигурацию, состоящую из четырех мигалок, — «светофор».
Судьба тетрамино
Самой увлекательной особенностью игры «Жизнь» была ее непредсказуемость. Не было другого способа узнать, что произойдет даже с самыми простыми фигурами, кроме отслеживания их жизни на протяжении многих поколений, что Конвей и его коллеги делали вручную. Живые клетки были фишками, которые размещались на доске для игры го с разметкой 19 × 19 линий. Когда для шаблона требовалось больше места, на полу укладывали дополнительные доски. Были найдены новые устойчивые конфигурации, получившие такие названия, как «батон», «корабль», «лодка» и «змея». Иногда исходный шаблон погибал или быстро менялся, превращаясь в одну из известных устойчивых конфигураций, а иногда начинал жить своей жизнью, что приводило всех в сильное волнение. Например, пентамино в форме буквы R состояло всего из пяти клеток, но продолжало эволюционировать на протяжении десятков поколений, пока на 69-м поколении не произошло исключительное событие. Эта конфигурация произвела на свет фигуру из пяти клеток, скользившую по доске.
Новая фигура получила имя «глайдер» (ее поведение проиллюстрировано на рисунке ниже). Через два поколения конфигурация переворачивается на другую сторону, а еще через два снова поворачивается таким образом, что оказывается на одну клетку ниже и на одну дальше от исходной позиции. Глайдер продолжает смещаться на одну клетку вниз и одну вперед каждые четыре поколения. Он будет двигаться в одном и том же направлении по диагонали до бесконечности, если ничто не преградит ему путь. «Главный систематик» Конвей выделил в игре «Жизнь» новый вид фигур, подобных глайдеру, которые перемещаются по прямым линиям, и назвал их космическими кораблями.
Глайдер
В 1970 году журналист Мартин Гарднер написал об игре «Жизнь» в своей многолетней рубрике в журнале Scientific American, что способствовало превращению математической игры Конвея в одно из первых компьютерных увлечений, охвативших весь мир [3]. Отслеживание эволюции фигур в игре «Жизнь» на доске для го требовало больших временных затрат и не было защищено от ошибок. Компьютеры позволяли отслеживать конфигурации гораздо дольше; кроме того, когда сменяющие друг друга поколения клеток мелькали на экране, фигуры как будто оживали [4]. Решетка с разбросанными по ней живыми клетками представляла собой первичную среду обитания изменчивых, постоянно преобразующихся конфигураций. Например, R-образное пентамино искрилось и пенилось на протяжении целых 1103 поколений, оставляя после себя обломки в виде корабля, лодки, батона, четырех ульев, четырех мигалок, шести глайдеров и восьми блоков. Запрограммировать игру «Жизнь» не составляло труда, поскольку в ней было всего четыре правила; тем не менее эта игра демонстрировала слишком сложное поведение, и его еще не удавалось добиться на компьютерах. Создание шаблонов и наблюдение за их дальнейшей жизнью вызывали такую зависимость, что, по оценкам Гарднера, это обошлось американской экономике в миллионы долларов компьютерного времени. Один читатель рассказал Гарднеру, что установил под своим рабочим столом секретную кнопку, для того чтобы переключать компьютер на игру «Жизнь», когда коллеги выходят из кабинета.
В Массачусетском технологическом институте (МТИ) игра «Жизнь» стала образом жизни. Одна сплоченная группа склонных к анархии и веселью, но очень умных студентов поставила перед собой цель изучить эту игрушечную вселенную глубже, чем кто-либо другой [5]. Это были первые компьютерные хакеры, настоящие техногики25. Общинная, антиавторитарная позиция хакеров оказала огромное влияние на формирование зарождающейся компьютерной культуры Америки, задавая тон новаторам более позднего периода, таким как Стив Джобс и Билл Гейтс. «План состоял в том, чтобы просто собрать всю эту дичь и одомашнить ее», — объяснил Билл Госпер, король хакеров, который преподает сейчас математику в Лос-Альтосе. Госпер проводил целые ночи в компьютерном зале MIT, играя в «Жизнь», и так продолжалось почти два года.
Конвей опубликовал на страницах журнала Scientific American задачу и предложил за ее решение приз в размере 50 долларов. Существует ли конфигурация, которая продолжает расти и у которой общее количество живых клеток увеличивается бесконечно? Госпер нашел такую конфигурацию и получил приз. «Глайдерное ружье» — это фигура из 36 живых клеток, пульсирующая как бьющееся сердце, порождая новый глайдер через каждые 30 поколений. Эти глайдеры один за другим отдаляются от исходной фигуры по диагонали, подобно бесконечному потоку пуль, выстреливаемых из ружья. Открытие глайдерного ружья сместило фокус изучения игры «Жизнь» с зоологии на физику. Госпер и его друзья-натуралисты больше не занимались пассивным исследованием флоры и фауны, переключившись на баллистику и изобретение фигур, в состав которых входят глайдерные ружья, стреляющие в другие фигуры. Можно было выстрелить двумя глайдерами друг в друга таким образом, что оба исчезали, не оставив после себя никаких обломков, как будто каким-то волшебным образом растворяясь в воздухе. «Мы пытались найти способ создавать что-то новое, сталкивая глайдеры между собой и наблюдая, что из этого выйдет, — объяснял Госпер. — А затем возникал другой вопрос: что произойдет, если ударить глайдерами по фигурам, полученным в результате столкновения глайдеров?» В ходе поиска ответа на этот вопрос Госпер открыл новую устойчивую конфигурацию из семи клеток под названием «пожиратель». Когда глайдер сталкивается с пожирателем, первый исчезает, а второй восстанавливается до исходного состояния, что создает впечатление, будто он поглотил глайдер. Кроме того, пожиратель поглощает другие устойчивые фигуры, расположенные рядом с ним, всегда восстанавливаясь после первоначального взаимодействия.
Пожиратель был первым признаком того, что игре «Жизнь» можно найти применение в реальном мире, например в проектировании объектов, которые способны к самовосстановлению. Нельзя сказать, что Госпера интересовало именно это. Для него было важно то, что глайдерное ружье и пожиратель позволяют вывести игру «Жизнь» на новый уровень — уровень разработки больших проектов, в рамках которых огромные конфигурации можно было бы создавать из сотен глайдеров, скачущих между разными элементами, а пожирателей разместить таким образом, чтобы они подбирали ненужные обломки. Первой конфигурацией подобного типа, которую Госперу удалось составить, был так называемый размножитель — фигура, порождающая глайдеры. Он начинает где-то с 50 глайдеров и ускоряет их воспроизведение так быстро, что примерно на 6500-м поколении количество глайдеров превышает количество поколений.
По мере увеличения банка знаний любители игры «Жизнь» выстраивали все более удивительные конфигурации. Одна из моих любимых представляет собой имитацию решета Эратосфена — метода поиска простых чисел, используемого древними греками. Решето, смоделированное в игре «Жизнь», состоит в основном из ружей, глайдеров и пожирателей. Его исходная конфигурация включает 5169 живых клеток [6]. Основной элемент решета — ружье, выстреливающее фигуру из 9 клеток под названием «легкий космический корабль» в горизонтальном направлении, через равные промежутки времени. Глайдеры обстреливают космические корабли, из которых выживают только второй, третий, пятый, седьмой, одиннадцатый и т. д. — другими словами, корабли, порядковый номер которых — простое число. (Подробное разъяснение того, как это работает, можно найти в Приложении 8.)