Искусство большего. Как математика создала цивилизацию - Майкл Брукс
Шрифт:
Интервал:
Закладка:
В его конструкции используются три оператора, которые теперь называются И (AND), ИЛИ (OR) и НЕ (NOT). Первые два работают с двумя утверждениями, каждое из которых может быть ИСТИННЫМ или ЛОЖНЫМ (или, как отметил Буль, 0 или 1). Оператор И дает результат ИСТИННО, только если ИСТИННЫ оба утверждения. Оператор ИЛИ дает результат ИСТИННО, если ИСТИННО одно из утверждений или если ИСТИННЫ оба. Оператор НЕ работает лишь с одним утверждением и дает результат ИСТИННО, если утверждение ЛОЖНО, и наоборот.
Логические операции Джорджа Буля, представленные в виде схем и “таблиц истинности” различных результатов
Буль опубликовал свою работу в 1854 году под названием “Исследование законов мышления, на которых основываются математические теории логики и вероятностей”[209]. Он так гордился ею, что считал, что именно благодаря ней он и войдет в историю, как в итоге и произошло. Например, оттолкнувшись от нее, Джон Венн в 1880 году изобрел новый тип диаграммы[210]. Венн назвал его кругами Эйлера, но сегодня они называются по фамилии создателя и используются для визуализации работы операторов И, ИЛИ и НЕ. Работа Буля также легла в основу современных компьютерных вычислений. Вытащите какую-нибудь микросхему Intel из своего компьютера, положите ее под мощный микроскоп, увеличьте изображение – и увидите транзисторы (по сути, переключатели), в которых задействованы электрические схемы, называемые логическими вентилями, поскольку они контролируют поток электрического тока. Эти вентили выполняют логические операции И, ИЛИ и НЕ, описанные Булем. Существует несколько способов соединять вентили в полезные комбинации, например в вентили “исключающее ИЛИ” (XOR), которые дают результат ИСТИННО, только если два утверждения различаются между собой, а также в вентили НЕ И (NAND), дающие результат ИСТИННО во всех случаях, кроме тех, когда оба утверждения ИСТИННЫ.
Булева логика в виде диаграмм Венна
Хотя сегодня может показаться, что никакого прорыва в этом нет, Булевы законы мышления стали проявлением радикально нового подхода к математике и позволили зашифровать то, что прежде шифрованию не поддавалось. Они принесли Булю множество почетных ученых степеней и членство в Королевском обществе. Впрочем, он недолго наслаждался успехом: он умер всего через десять лет после публикации своих выводов.
Печально, что виновницей его смерти почти наверняка стала его жена. У нее не было злого умысла – их брак был поразительно счастливым, несмотря на 17-летнюю разницу в возрасте. Но, к несчастью, Мэри верила в гомеопатию: она считала, что подобное лечится подобным. Однажды в ноябре 1864 года Джордж пришел домой, промокнув до нитки под ливнем и дрожа от холода. Мэри уложила его в постель и стала поливать холодной водой. У него началась простуда, а затем воспаление легких. Через несколько дней он умер.
Несмотря на награды, которые посыпались на Буля, в полной мере потенциал его алгебры логики оценили лишь через семьдесят три года. И сделал это – неожиданно – инженер по имени Клод Элвуд Шеннон, мастер жонглировать и кататься на одноколесном велосипеде.
Телефонные номера
Признание Джорджа Буля началось с очередной чрезвычайно весомой магистерской диссертации. Да, диссертация Билла Хьюлетта основала Кремниевую долину, но диссертация Шеннона, написанная в 1937 году и озаглавленная “Символический анализ релейных и переключательных схем”, сотворила всю информационную эпоху[211]. Она родилась из первой работы, которую он получил после окончания бакалавриата по электроинженерии и математике в Мичиганском университете: он устроился в Массачусетский технологический институт (MIT), где загружал дифференциальные уравнения в “дифференциальный анализатор” – один из первых механических компьютеров. Этот аппарат стоял на кафедре инженерии MIT, и Шеннон вручную задавал положения более чем 100 электромеханических переключателей, называемых реле. Такие же реле – в огромном множестве – были основой новой отрасли телекоммуникаций, и, поработав в MIT в 1937 году, Шеннон смог на лето устроиться в Лаборатории Белла при Американской телефонной и телеграфной компании (AT&T). Там он погрузился в поиск нового способа выполнять нудную и отнимающую уйму времени задачу по разработке и проверке гигантских сетей релейных схем для быстрорастущей американской телефонной системы. Так Шеннон и открыл для себя работу Джорджа Буля.
Преобразовав состояния реле ВКЛ/ВЫКЛ в 1/0, Шеннон применил инновационные идеи Буля для разработки бинарной математики, которая представляла во всей полноте переключательную сеть телефонной системы. Теперь, вместо того чтобы конструировать и по несколько раз испытывать тысячи переключателей, инженеры могли с помощью Булевой алгебры записывать конфигурации и вычислять, насколько хорошо они будут работать, когда окажутся собраны.
Преимущества такого подхода стали очевидны сразу, и Шеннон получил престижную награду за статью об этой схеме[212]. Когда он подал заявку на выступление на конференции Американской ассоциации инженеров-электриков, организаторы написали его научному руководителю и назвали работу Шеннона “выдающейся”. Руководителем Шеннона был Вэнивар Буш, декан Инженерной школы MIT и создатель дифференциального анализатора. К июню 1940 года, когда в Европе началась война, Буш создал новую структуру – Национальный исследовательский комитет по вопросам обороны США (NDRC). Многие из контрактов на проведение военных исследований, распределявшихся Бушем, уходили в Лаборатории Белла, где теперь работал Шеннон.
Одним из первых заданий Шеннона для NDRC было участие в разработке “системы X”, защищенной телефонной линии, позволяющей президенту Франклину Д. Рузвельту вести конфиденциальные переговоры с британским премьер-министром Уинстоном Черчиллем. В представлении инженеров трансатлантический телефонный звонок – это не более чем колеблющаяся электромагнитная волна, и инженеры Лабораторий Белла понимали, что разговор можно зашифровать, если смешать эту волну с несколькими другими, известными лишь людям на другом конце провода. Отправитель мог добавлять сигналы, а получатель мог их удалять, очищая изначальную передачу. Но вскоре инженеры поняли, что математика добавления непрерывных волн осложняет надежное шифрование сигнала: достаточно подготовленный перехватчик вполне мог выяснить, о чем идет разговор. Проблему решили с помощью цифрового подхода.
Сначала сигнал разбили на последовательность дискретных единиц, каждую из которых маркировали числом, описывающим амплитуду волны в конкретный момент. Это позволило им добавлять к передаче случайные числа, известные только отправителю и получателю сигнала. Теперь для перехватчика стало математически невозможно получить доступ к информации.
Работая над “системой X”, Шеннон увлекся технологиями шифрования. Он даже беседовал о них с британским математиком Аланом Тьюрингом, который участвовал во взломе немецкого шифра “Энигма” и в 1943 году посетил Лаборатории Белла, чтобы изучить американские инновации в области шифрования. Как выяснилось, взгляды Тьюринга и Шеннона на оптимальные способы шифрования не совпадали, поэтому в своих разговорах за чаем они почти
