Булева логика в виде диаграмм Венна
Хотя сегодня может показаться, что никакого прорыва в этом нет, Булевы законы мышления стали проявлением радикально нового подхода к математике и позволили зашифровать то, что прежде шифрованию не поддавалось. Они принесли Булю множество почетных ученых степеней и членство в Королевском обществе. Впрочем, он недолго наслаждался успехом: он умер всего через десять лет после публикации своих выводов.
Печально, что виновницей его смерти почти наверняка стала его жена. У нее не было злого умысла – их брак был поразительно счастливым, несмотря на 17-летнюю разницу в возрасте. Но, к несчастью, Мэри верила в гомеопатию: она считала, что подобное лечится подобным. Однажды в ноябре 1864 года Джордж пришел домой, промокнув до нитки под ливнем и дрожа от холода. Мэри уложила его в постель и стала поливать холодной водой. У него началась простуда, а затем воспаление легких. Через несколько дней он умер.
Несмотря на награды, которые посыпались на Буля, в полной мере потенциал его алгебры логики оценили лишь через семьдесят три года. И сделал это – неожиданно – инженер по имени Клод Элвуд Шеннон, мастер жонглировать и кататься на одноколесном велосипеде.
Признание Джорджа Буля началось с очередной чрезвычайно весомой магистерской диссертации. Да, диссертация Билла Хьюлетта основала Кремниевую долину, но диссертация Шеннона, написанная в 1937 году и озаглавленная “Символический анализ релейных и переключательных схем”, сотворила всю информационную эпоху[211]. Она родилась из первой работы, которую он получил после окончания бакалавриата по электроинженерии и математике в Мичиганском университете: он устроился в Массачусетский технологический институт (MIT), где загружал дифференциальные уравнения в “дифференциальный анализатор” – один из первых механических компьютеров. Этот аппарат стоял на кафедре инженерии MIT, и Шеннон вручную задавал положения более чем 100 электромеханических переключателей, называемых реле. Такие же реле – в огромном множестве – были основой новой отрасли телекоммуникаций, и, поработав в MIT в 1937 году, Шеннон смог на лето устроиться в Лаборатории Белла при Американской телефонной и телеграфной компании (AT&T). Там он погрузился в поиск нового способа выполнять нудную и отнимающую уйму времени задачу по разработке и проверке гигантских сетей релейных схем для быстрорастущей американской телефонной системы. Так Шеннон и открыл для себя работу Джорджа Буля.
Преобразовав состояния реле ВКЛ/ВЫКЛ в 1/0, Шеннон применил инновационные идеи Буля для разработки бинарной математики, которая представляла во всей полноте переключательную сеть телефонной системы. Теперь, вместо того чтобы конструировать и по несколько раз испытывать тысячи переключателей, инженеры могли с помощью Булевой алгебры записывать конфигурации и вычислять, насколько хорошо они будут работать, когда окажутся собраны.
Преимущества такого подхода стали очевидны сразу, и Шеннон получил престижную награду за статью об этой схеме[212]. Когда он подал заявку на выступление на конференции Американской ассоциации инженеров-электриков, организаторы написали его научному руководителю и назвали работу Шеннона “выдающейся”. Руководителем Шеннона был Вэнивар Буш, декан Инженерной школы MIT и создатель дифференциального анализатора. К июню 1940 года, когда в Европе началась война, Буш создал новую структуру – Национальный исследовательский комитет по вопросам обороны США (NDRC). Многие из контрактов на проведение военных исследований, распределявшихся Бушем, уходили в Лаборатории Белла, где теперь работал Шеннон.
Одним из первых заданий Шеннона для NDRC было участие в разработке “системы X”, защищенной телефонной линии, позволяющей президенту Франклину Д. Рузвельту вести конфиденциальные переговоры с британским премьер-министром Уинстоном Черчиллем. В представлении инженеров трансатлантический телефонный звонок – это не более чем колеблющаяся электромагнитная волна, и инженеры Лабораторий Белла понимали, что разговор можно зашифровать, если смешать эту волну с несколькими другими, известными лишь людям на другом конце провода. Отправитель мог добавлять сигналы, а получатель мог их удалять, очищая изначальную передачу. Но вскоре инженеры поняли, что математика добавления непрерывных волн осложняет надежное шифрование сигнала: достаточно подготовленный перехватчик вполне мог выяснить, о чем идет разговор. Проблему решили с помощью цифрового подхода.
Сначала сигнал разбили на последовательность дискретных единиц, каждую из которых маркировали числом, описывающим амплитуду волны в конкретный момент. Это позволило им добавлять к передаче случайные числа, известные только отправителю и получателю сигнала. Теперь для перехватчика стало математически невозможно получить доступ к информации.
Работая над “системой X”, Шеннон увлекся технологиями шифрования. Он даже беседовал о них с британским математиком Аланом Тьюрингом, который участвовал во взломе немецкого шифра “Энигма” и в 1943 году посетил Лаборатории Белла, чтобы изучить американские инновации в области шифрования. Как выяснилось, взгляды Тьюринга и Шеннона на оптимальные способы шифрования не совпадали, поэтому в своих разговорах за чаем они почти не затрагивали рабочих тем, а рассуждали о том, какими возможностями могут обладать компьютеры. Они сошлись во мнении, что компьютеры теоретически могут имитировать работу человеческого мозга и что на реализацию этого на практике уйдет пара десятков лет. Очевидно, эта идея не давала Тьюрингу покоя и после войны, поскольку в 1948 году он написал революционную статью “Разумные машины”[213]. Шеннон, однако, отвлекся. Его прорывная статья 1948 года называлась “Математическая теория связи”[214]. Построив ее на базе своей выдающейся магистерской диссертации, он подробно описал в ней все, что произойдет в технологиях связи в последующие семьдесят лет.
Первый элемент статьи Шеннона – идея о том, что информацию можно моделировать на основе статистического подхода. Шеннон отмечает, что одни комбинации слов более вероятны, чем другие: например, вы вряд ли ожидаете, что после слова “стол” я поставлю слово “депресняк”. Мы воплотили это в умной (но далеко не безупречной) технологии интеллектуального ввода текста на наших телефонах, но именно Шеннон первым продемонстрировал, что благодаря этому у нас появляется возможность для более эффективной коммуникации. По сути, это позволяет “сжимать” многие формы коммуникации. Например, мы можем отказаться от передачи некоторых фрагментов информации, поскольку человек, выступающий получателем, сумеет без труда их восстановить. Английский язык прекрасно подходит для этой задачи: его гласные часто избыточны. Как Шеннон отметил в статье для “Британской энциклопедии”, MST PPL HV LTTL DFFCLTY N RDNG THS SNTNC[215].
Второй элемент – идея об информационной энтропии. Шеннон зацепился за возможность оцифровки сигнала с целью сведения его к последовательности поддающихся манипуляции чисел. Он также нашел способ количественного представления информации, содержащейся в сигнале, что интересовало и Тьюринга. Тьюринг назвал единицу информации “бан”, но Шеннон выбрал вариант, предложенный коллегой в конце 1946 года, когда они обменивались идеями за обедом. Двоичная единица не может называться “баном”, “биджитом” или “бинитом”, сказал Джон Тьюки. “Разве не очевидно, что ее нужно назвать бит?”[216]
Но как понять, сколько у вас битов? Здесь Шеннон оттолкнулся от малоизвестной работы инженера Ральфа Хартли. Хартли более десяти лет проработал в Western Electric Company над телеграфной и голосовой передачей и после этого в 1928 году опубликовал примечательную статью “Передача информации”[217]. Он понял, что информацию можно представлять количественно, на каком бы языке и посредством какой бы технологии ни происходила передача, если понять, какие решения лежат в ее основе. Подбрасывая монетку, вы совершаете выбор. Говоря с кем-нибудь по-английски, вы много раз выбираете слова английского языка. Если вы хотите написать английское слово из трех букв, вам придется три раза сделать выбор из 26 вариантов. Зная диапазон вариантов, отметил Хартли, можно получить меру информации, необходимой для осуществления связи. Он добавил, однако, что такой показатель не будет непосредственным. Работая с алфавитом, вы выбираете из 17 576 (26 × 26 × 26) вариантов. Хартли, впрочем, подчеркнул, что в трехбуквенном слове не содержится столько информации. Он предложил определять объем информации – сколько раз нужно сделать бинарный (да/нет) выбор – с помощью логарифма (по основанию 2) от общего числа вариантов.
Логарифм по основанию 2 от 17 576 равен 14,1. Это значит, что для передачи английского трехбуквенного слова нам нужно сделать выбор не более 15 раз. Иными словами, размер сообщения составляет 15 бит.
Глядя на биты, можно увидеть, как происходит взаимодействие между ними. Один бит дает нам только два варианта: 0 или 1. Два бита дают четыре варианта: 00, 01, 10, 11. Три бита дают восемь вариантов: 000, 001, 010, 011, 100, 101, 110, 111.
Четыре бита дают 16 вариантов. Можно также повернуть счет с ног на голову и сказать, что в процессе выбора одного из 16 одинаково вероятных сообщений задействуется четыре бита информации. Здесь наблюдается логарифмическая связь: 4 – это логарифм по основанию 2 от 16.
В общем виде правило таково: при наличии C одинаково вероятных вариантов вероятность выбора каждого сообщения равна 1/С. Информация, участвующая в процессе выбора, – это логарифм по основанию 2 от 1/