В течение четверти века великий стэнфордский почётный профессор проводит в декабре особую лекцию «У рождественской ёлки». Приближающийся к своим 82 годам Дональд Кнут снова провёл юбилейную 25-ю лекцию 5 декабря. Он напомнил аудитории, что по-прежнему усердно продолжает работать над книгой, которую пишет последние 57 лет.

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

Поэтому вдвойне необычно увидеть этого великого человека вживую.

У нашего сайта есть собственная рождественская традиция: мы публикуем обзоры и скриншоты с последних лекций Кнута. В 2017 году я описал это как «встречу с любимым родственником на праздники» и «шанс увидеть вживую великий ум».

Лекция этого года не стала исключением.

Просто как пи

Лекция Кнута проводилась 5 декабря, но была опубликована только в субботу 21 декабря. (К понедельнику она уже набрала более 2 000 просмотров.)


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


Пятое издание четвёртого тома было выпущено в прошлом месяце.

Похоже, Кнуту тоже очень понравилась лекция. «Благодарю всех за то, что вы пришли», — сказал Кнут аудитории. «Похоже, вы от меня ещё не устали, — пошутил он, добавив, — посмотрим, придёт ли кто-нибудь в следующем году...»

Но для лекции этого года Кнут подготовил нечто особенное. Он показал аудитории как на протяжении половины столетия причудливо встраивал цифры числа пи в разные упражнения своей книги, снова, и снова, и снова. Кнут рассказал слушателям, что выполнил поиск по всему тексту своей книги «Искусство программирования» при помощи Linux-инструмента egrep, и нашёл целых 1 700 вхождений слова «пи», то есть пока оно встречается примерно дважды на протяжении каждых пяти страниц книги. Он считает, что использование числа пи в примерах позволяет читателям убедиться, что алгоритмы действительно работают даже для произвольно выбранного множества цифр.

Вскоре его речь превратилась в своего рода интеллектуальный аттракцион — он поделился другими фактами, связанными с пи, которые часто удивляли, а иногда и ошеломляли.

Он начал с демонстрации обложки книги The Numerology of Dr. Matrix математика Мартина Гарднера, и показал его таблицу первых 32 десятичных знаков пи. Кнут вспоминал, как включил её в один из ранних томов «Искусства программирования» и процитировал утверждение Гарднера о том, что правильная интерпретация цифр пи передаёт всю историю человечества. «В каком-то смысле можно сказать, что основная цель моей жизни заключается в правильной интерпретации знаков пи», — сказал Кнут аудитории. «Что ещё более важное можно было бы сделать за свою жизнь?»

Однако в описании видео говорится, что «в лекции рассказывается о множестве интерпретаций этих знаков, и правильных, и неправильных».

Далее Кнут поделился мнемоническим правилом для запоминания первых цифр пи. Можно получить каждую из его первых цифр — 3,14159265358979 — сосчитав количество букв в каждом слове фразы:

«How I need a drink — alcoholic, of course — after the heavy lectures involving quantum mechanics». [прим. пер.: аналог на русском — «Как я хочу и желаю надраться до чертей после сих тупых докладов, наводящих тяжелую депрессию».]

Затем он продемонстрировал книгу, которую назвал «одним из величайших достижений литературы УЛИПО» — вида литературы, в котором писатели следуют строгим (а иногда и математическим) ограничениям. Как же она называется?

Not A Wake: A Dream Embodying (pi)’s Digits Fully For 10000 Decimals


Количество букв в каждом слове этого названия тоже точно соответствует последовательности цифр пи. Кнут процитировал написанное на задней стороне обложки: «It’s a play, a story, fantasies in modern verse and other writings, following without exception of the textbook math motifs». Это предложение тоже состоит из слов, длина которых соответствует цифрам числа пи. «Автор книги, — добавляет Кнут, — доходит в ней до 10 000 цифр». Затем он прочитал первую поэтическую страницу книги:

«Now I fall, a tired suburbian in a liquid under the trees
Drifting alongside forests simmering red in the twilight over Europe...»


Цифра 0 обозначается десятибуквенными словами, а 11 может быть представлено одиннадцатибуквенными словами. «Автор назвал этот язык Pi-lish», — сообщил Кнут со смехом. А как насчёт знаменитой последовательности из шести девяток подряд? Поэт написал:

«Blameless, bloodless, guiltless, ceaseless, limitless, boundless».

Аудитория зааплодировала, а Кнут продолжил чтение книги. В ней есть эссе, короткие стихотворения, эпиграммы и даже сценарий с диалогами для научно-фантастического эпического фильма под названием Zompyr Chronicle. Каждое слово при этом имеет длину, точно равную соответствующему знаку пи.

«Однако настоящим высшим пилотажем стал кроссворд».

Постойте-ка, что? Да, строго придерживаясь длины слов, задаваемой каждой цифрой пи, одна из страниц книги внезапно превращается в подсказки к кроссворду. За ней следует сам кроссворд, куда нужно вписывать ответы. Его название даёт понять, что слова-ответы являются названиями книг с переставленными первыми буквами слов. И в самом деле, в подсказках и ответах зашифрованы классическая книга Уолта Уитмена «Тристья лавы» («Greaves of Lass») и революционный роман Джеймса Джойса «Фоминки по Пиннегану» («Winnegan’s Fake»).

А ближе к концу книги встречается даже идеальный шекспировский сонет…

Затем Кнут признался, что в указателе тома 4A его собственной книги есть особо хитрая отсылка к числу пи: «нужно понять, что же на странице 382 выглядит, как пи»…

Правильный ответ: +00++-+++-000-

Это пи в «одной из самых потрясающих систем счисления» — симметричной троичной системе (balanced ternary number system), в которой символы 0,+ и — используются для представления чисел в системе с основанием 3.

Загадки с пи

Далее Кнут обратился к предварительным гранкам только что изданной пятой редакции четвёртого тома. Он сообщил, что на любой странице вы скорее всего найдёте головоломку, потому что «оказалось, что описываемые здесь виды алгоритмов лучше всего иллюстрируются их связью с головоломками». И упор в книге делается не на том, как решать головоломки, а на том, как создавать их. В качестве примера он продемонстрировал зрителям созданную им головоломку судоку, в которой готовыми цифрами были 3, 1, 4, 1, 5, 9…

«Мне удалось уместить сюда первые 32 знака пи».


Можно ли создать судоку более чес с 32 цифрами пи? Нет, и на то есть простая причина — 33-м символом пи является ноль, единственная цифра, не используемая в судоку.

Затем Дональд показал обложку книги Exotische Sudoku, где для судоку не только использовались разряды пи, но их ещё и выстроили по кругу. Эта книга целиком состоит из головоломок судоку, где в качестве подсказок используются знаки пи с соблюдением дополнительного условия — две диагональные линии из девяти квадратов в решении тоже должны один раз содержать каждую цифру.


Кнут также показал примеры двух головоломок с участием шахматных фигур. В решении «Knight Sudoko» каждая строка, столбец и квадрат содержат ровно трёх шахматных коней. В подсказках показаны только некоторые из коней вместе с числом, указывающим, сколько других коней они могут атаковать. Разумеется, Кнут создал головоломку, в которой эти числа равны 3, 1, 4, 1, 5…

Также существует похожая головоломка с использованием слонов, разумеется, подсказки в ней тоже составляют число пи.

Затем Кнут обратился к головоломкам KenKen, в которых числа каждого набора соединённых квадратов сочетаются, давая нужное решение (с помощью заданного математического оператора). В версии Кнута числа-подсказки — это 3, 14, 15, 9, 2 и 6… Ещё существует головоломка Kakuro — разновидность кроссворда с числами; Кнут предложил читателям создать такую задачу, где ответами бы были 31, 41, 59, 26, 53, 58, 97. В головоломке Hidato последовательные числа располагаются на сетке, но только в соседних квадратах (по горизонтали, вертикали или диагонали). Кнут предложил читателям создать точно такую же головоломку с разрядами числа пи.

Это замечательный способ демонстрации того, что алгоритмы на самом деле будут работать с любым набором чисел, даже 3,141592. В качестве грандиозного завершения Кнут рассказал наверное о самой интересной головоломке из всех — «китайской стене» (slitherlink). Решающие её должны нарисовать одну непрерывную линию, соединяющую точки сетки, касаясь количества сторон «квадрата» точек, задаваемого номером квадрата. Книга Кнута задаёт читателям вопрос — какой сюрприз заключён в одном конкретном решении «китайской стены»?

Когда Кнут рассказал об удивительном решении головоломки, то заслужил долгие аплодисменты.


«Большое спасибо, — торжественно сказал он аудитории, — и счастливого Рождества».