5 и т. д. К тому времени, когда мы достигнем шестьдесят четвертой ступеньки, мы окажемся далеко, далеко, далеко, далеко в стране больших чисел и не сможем понять, где мы. Зато мы наконец пришли к цели: g64 — это и есть число Грэма.
Невелика точность, если ответ на математический вопрос лежит где-то между числом 6 и неимоверно большим числом g64? Рон Грэм соглашался с этим, но для него это подчеркивало разрыв между тем, что вы считаете истиной, и тем, что вы можете доказать. Мы знаем, что существует точный ответ на первоначальный вопрос Грэма и Ротшильда, и он скрывается где-то на этом невероятно огромном интервале, но найти его точно? Что ж, удачи. На самом деле этот интервал значительно сократился с тех пор, как Грэм и Ротшильд написали свою статью. Сейчас мы знаем, что ответ находится где-то между 13 и 2 ↑ ↑ ↑ 5. Это улучшение, но его явно не хватит, чтобы удовлетворить требования разгневанной инопланетной расы, проверяющей человечество с помощью проблем из теории Рамсея.
В истории математики число Грэма — настоящий левиафан, но я боюсь, что его великолепие теряется из-за абстракции. Чтобы лучше понять его, мы обратимся к физике и выясним, почему это число настолько велико, что способно убить.
Что делает число Грэма таким опасным? Почему ваша голова сколлапсирует, если вы будете размышлять о его десятичном представлении? Оказывается, в таком изображении числа Грэма есть энтропия — много энтропии, — а каждый раз, когда вы пытаетесь втиснуть слишком много в слишком маленькое пространство, неизбежно образуются черные дыры. Может показаться странным, что число способно нести энтропию так же, как яйцо или трицератопс, однако энтропия тесно связана с информацией, а последняя в числе Грэма, безусловно, содержится. Если бы я назвал вам его последнюю цифру, у вас появилось бы новое знание. Если бы я назвал вам его полное десятичное представление, вашей голове пришлось бы втискивать гораздо больше информации. Поглощение такого большого количества энтропии в замкнутом пространстве приведет к единственному возможному результату: смерти от превращения головы в черную дыру.
Чтобы понять связь между черными дырами, энтропией и десятичным представлением числа Грэма, нам нужно изучить смысл информации. Мне известна последняя цифра числа Грэма, и я предлагаю вам узнать ее. Вы можете задавать мне какие угодно вопросы, но я буду отвечать только «да» и «нет». Предположим, вы придерживаетесь следующей стратегии.
Это цифра от 0 до 4? Нет.
Это 5, 6 или 7? Да.
Это 5 или 6? Нет.
Вы понимаете, что ответ — семерка.
Вы узнали это за три вопроса. Стратегия была удачной: с каждым новым вопросом круг возможных цифр существенно уменьшался. В среднем такая стратегия определит случайно выбранную цифру за 3,32 вопроса. Именно таким методом Клод Шеннон, криптограф и пионер теории информации, предложил измерять количество информации: минимальное число ответов «да» или «нет», необходимое, чтобы точно определить то, что вы хотите знать.
Шеннон сочетал очевидный талант к вычислительной технике и математике с практическими навыками первоклассного инженера. Он всегда что-то мастерил: от летающих тарелок-фрисби с ракетным двигателем до одноколесных велосипедов и жонглирующих роботов. Самое хулиганистое его творение — машина, при включении выдвигавшая механическую руку, которая тут же отключала машину. Шеннон также дружил с Роном Грэмом; эта дружба выросла из интереса Шеннона к жонглированию: старик хотел научиться этому искусству, а Грэм согласился быть преподавателем. В итоге Шеннон умел жонглировать четырьмя мячами — на один больше, чем могли осилить его роботы.
Интерес Шеннона к теории информации произрастает из его работ военного времени над кодами и коммуникациями в компании Bell Telephone Laboratories в Нью-Джерси. Он понимал важность передачи информации, особенно во время войны, и что нередко она трудна или даже опасна. Шеннон хотел выяснить, как эффективно передать сообщение, когда мешает сильный «шум», и для этого ему потребовалось определить хорошую меру для количества информации.
Чтобы понять его меру, подбросьте монетку. Чтобы определить результат броска, вам нужен всего один ответ вида «да» или «нет» — достаточно спросить: выпал орел? Таким образом, один бросок монеты несет один бит информации. Пять бросков монеты дают пять бит, гугол бросков даст гугол бит. В общем виде нам нужно связать количество битов не с количеством монет, а с количеством возможных исходов. При пяти подбрасываниях монеты можно получить 2 × 2 × 2 × 2 × 2 = 32 различных исхода. Как извлечь пять бит из этих 32 исходов? Поскольку 32 = 25, пять бит находятся в показателе степени. В случае последней цифры числа Грэма возможны десять разных исходов (последней может оказаться любая цифра от 0 до 9). Сколько это битов? Ситуация немного сложнее, поскольку 10 больше, чем 23, но меньше, чем 24, поэтому ответ лежит где-то между тремя и четырьмя битами. Оказывается, знание последней цифры числа Грэма несет примерно 3,32 бита информации[67].
Конечно, Шеннона больше интересовали слова и предложения, а не подбрасывание монеты. Самое длинное слово, встречающееся в основных словарях английского языка, — pneumonoultramicroscopicsilicovolcanoconiosis. Это термин для заболевания легких, вызванного вдыханием вулканического кремнезема после извержения. Не идеальная судьба, но, надо полагать, лучше, чем взорвавшаяся голова. Нас интересует, сколько информации содержится в самом этом слове. Поскольку в английском алфавите 26 букв, мы могли бы сказать, что каждая буква — один из 26 возможных исходов. Поскольку это число находится между 16 = 24 и 32 = 25, мы получаем оценку: в каждой букве содержится от 4 до 5 бит информации. Более точный подсчет дает величину 4,7 бита информации[68]. Все наше слово состоит из впечатляющих сорока пяти букв, так что получаем 211,5 бита. Хотя это разумная оценка общего объема информации, содержащейся в нашем слове, в реальности она завышена. В английском языке, как и в любом другом, есть определенные закономерности и правила. Например, рассмотрим слово quicquidlibet, которое буквально означает все, что угодно. В нем вы дважды встречаете букву q и в обоих случаях почти наверняка знаете, что следующей будет u[69]. Разве можно сказать, что чтение буквы u дает вам 4,7 бита информации, если вы уже заранее знали, что именно она и должна появиться?
Такие тонкости говорят нам о том, что вычислять информацию сложнее, чем просто смотреть на возможные исходы: нужно учитывать еще и вероятности. Например, если вы пять раз подбросите симметричную монету, вы действительно получите пять бит информации. А если монета несимметрична и всегда падает орлом? Можете ли вы утверждать, что получили какую-то информацию, увидев, как пять раз подряд выпал орел? Конечно, нет.
Шеннон придумал формулу для информации, которая все это учитывает. Согласно ей, если вы подбросите монету, у которой с вероятностью p выпадает орел, а с вероятностью q = 1 — p выпадает решка, то вы получаете — plog2p — qlog2q бит информации. Формула включает логарифмы по основанию 2, потому что Шеннон вычислял информацию в формате бинарных (двоичных) исходов. Она работает именно так, как вы интуитивно ожидаете. Например, если монета честная, то p = q = 0,5, и подбрасывание дает один бит информации. Если монета абсолютно перекошена в сторону орла (p = 1, q = 0) или решки (p = 0, q = 1), то подбрасывание вообще не даст никакой информации. Все остальные варианты лежат между этими крайними случаями.
Но как насчет более сложных вещей, которые действительно интересовали Шеннона, например букв, слов или даже предложений? Как измерить информацию, содержащуюся в них? Что ж, предположим, у вас есть первые несколько букв какого-то неизвестного слова: CHE. Сколько информации содержится в следующей букве, когда она станет известной? Если бы все буквы были равновероятными, мы бы сказали: 4,7 бита. Однако мы знаем, что это неверно. Попробуйте ввести буквы CHE, набирая сообщение на мобильном телефоне. Какие слова появляются в качестве подсказки? Вот некоторые из наиболее вероятных.
CHEERS
CHEAT
CHECK
Это заставляет предположить, что любая из букв Е, А и С имеет более высокую вероятность появления, чем, скажем, В. Если условиться, что буква А встречается с вероятностью p1, буква В — с вероятностью p2, буква С — с вероятностью p3 и т. д., вплоть до Z, имеющей вероятность p26, то, согласно Шеннону, количество информации в следующей букве будет таким:
I = —p1log2p1 — p2log2p2 — p3log2p3 — … — p26log2p26.
Как обычно, она измеряется в битах. Шеннон проверял способности носителей английского языка угадывать следующую букву в слове. Его эксперименты показали, что в среднем каждая буква содержит от 0,6 до 1,3 бита информации. Может показаться, что это немного, но именно поэтому письменный английский хорош для общения. Если какая-нибудь буква пропущена или введена неправильно, вы не потеряете слишком много информации и, скорее всего, сможете расшифровать th mxssage (или, в случае русского языка, эт сожбщение).
Самое примечательное свойство формулы Шеннона — ее сходство с другой формулой, которую более полувека назад вывел физик