Удивительные числа Вселенной. Путешествие за грань воображения

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

Шеннон сочетал очевидный талант к вычислительной технике и математике с практическими навыками первоклассного инженера. Он всегда что-то мастерил: от летающих тарелок-фрисби с ракетным двигателем до одноколесных велосипедов и жонглирующих роботов. Самое хулиганистое его творение – машина, при включении выдвигавшая механическую руку, которая тут же отключала машину. Шеннон также дружил с Роном Грэмом; эта дружба выросла из интереса Шеннона к жонглированию: старик хотел научиться этому искусству, а Грэм согласился быть преподавателем. В итоге Шеннон умел жонглировать четырьмя мячами – на один больше, чем могли осилить его роботы.

Интерес Шеннона к теории информации произрастает из его работ военного времени над кодами и коммуникациями в компании Bell Telephone Laboratories в Нью-Джерси. Он понимал важность передачи информации, особенно во время войны, и что нередко она трудна или даже опасна. Шеннон хотел выяснить, как эффективно передать сообщение, когда мешает сильный «шум», и для этого ему потребовалось определить хорошую меру для количества информации.

Чтобы понять его меру, подбросьте монетку. Чтобы определить результат броска, вам нужен всего один ответ вида «да» или «нет» – достаточно спросить: выпал орел? Таким образом, один бросок монеты несет один бит информации. Пять бросков монеты дают пять бит, гугол бросков даст гугол бит. В общем виде нам нужно связать количество битов не с количеством монет, а с количеством возможных исходов. При пяти подбрасываниях монеты можно получить 2 × 2 × 2 × 2 × 2 = 32 различных исхода. Как извлечь пять бит из этих 32 исходов? Поскольку 32 = 2⁵, пять бит находятся в показателе степени. В случае последней цифры числа Грэма возможны десять разных исходов (последней может оказаться любая цифра от 0 до 9). Сколько это битов? Ситуация немного сложнее, поскольку 10 больше, чем 2³, но меньше, чем 2⁴, поэтому ответ лежит где-то между тремя и четырьмя битами. Оказывается, знание последней цифры числа Грэма несет примерно 3,32 бита информации[67].

Конечно, Шеннона больше интересовали слова и предложения, а не подбрасывание монеты. Самое длинное слово, встречающееся в основных словарях английского языка, – pneumonoultramicroscopicsilicovolcanoconiosis. Это термин для заболевания легких, вызванного вдыханием вулканического кремнезема после извержения. Не идеальная судьба, но, надо полагать, лучше, чем взорвавшаяся голова. Нас интересует, сколько информации содержится в самом этом слове. Поскольку в английском алфавите 26 букв, мы могли бы сказать, что каждая буква – один из 26 возможных исходов. Поскольку это число находится между 16 = 2⁴ и 32 = 2⁵, мы получаем оценку: в каждой букве содержится от 4 до 5 бит информации. Более точный подсчет дает величину 4,7 бита информации[68]. Все наше слово состоит из впечатляющих сорока пяти букв, так что получаем 211,5 бита. Хотя это разумная оценка общего объема информации, содержащейся в нашем слове, в реальности она завышена. В английском языке, как и в любом другом, есть определенные закономерности и правила. Например, рассмотрим слово quicquidlibet, которое буквально означает все, что угодно. В нем вы дважды встречаете букву q и в обоих случаях почти наверняка знаете, что следующей будет u[69]. Разве можно сказать, что чтение буквы u дает вам 4,7 бита информации, если вы уже заранее знали, что именно она и должна появиться?

Такие тонкости говорят нам о том, что вычислять информацию сложнее, чем просто смотреть на возможные исходы: нужно учитывать еще и вероятности. Например, если вы пять раз подбросите симметричную монету, вы действительно получите пять бит информации. А если монета несимметрична и всегда падает орлом? Можете ли вы утверждать, что получили какую-то информацию, увидев, как пять раз подряд выпал орел? Конечно, нет.

Шеннон придумал формулу для информации, которая все это учитывает. Согласно ей, если вы подбросите монету, у которой с вероятностью p выпадает орел, а с вероятностью q = 1 – p выпадает решка, то вы получаете – plog₂p – qlog₂q бит информации. Формула включает логарифмы по основанию 2, потому что Шеннон вычислял информацию в формате бинарных (двоичных) исходов. Она работает именно так, как вы интуитивно ожидаете. Например, если монета честная, то p = q = 0,5, и подбрасывание дает один бит информации. Если монета абсолютно перекошена в сторону орла (p = 1, q = 0) или решки (p = 0, q = 1), то подбрасывание вообще не даст никакой информации. Все остальные варианты лежат между этими крайними случаями.