Пара слов о формате “Код как борьба”. Здесь не будет подробных биографий - про каждого из героев этого цикла написаны отдельные толстые книги, и одна статья такую книгу не заменит. Не будет здесь и сухого технического разбора, кому это интересно. Вместо этого - попытка проследить, как одна идея вырастает из другой, как эстафета, которую передают друг другу через десятилетия и века люди, часто вообще не подозревающие, что работают над одним и тем же. Если какой-то сюжет или деталь захочется изучить подробнее - внизу статьи есть подборка книг, статей и первоисточников по теме.
Прошлые статьи цикла:
Почему обычный выключатель света вообще способен участвовать в математической логике?
Звучит как странный вопрос, правда? А ответ на него дал один студент в 1937 году и с тех пор мы буквально живём в мире, который он, по сути, спроектировал.
Это четвёртая статья цикла “Код как борьба: Кратчайшая история IT”. И, как я обещал в прошлый раз, сегодня будет заметно легче - никакой личной трагедии, как у Тьюринга, никакой атомной бомбы, как у фон Неймана. Сегодня у нас жонглирующий гений с механической мышью. Но начнём мы, как обычно, с чего-то серьёзного.
Погнали
Часть первая. Магистерская диссертация, которую называют самой важной студенческой работой века
Клод Шеннон родился в 1916 году в городке Петоски, штат Мичиган, вырос в соседнем Гейлорде. Получил сразу два диплома одновременно в Мичиганском университете - по электротехнике и по математике в 1936 году. А потом поступил в аспирантуру MIT.
И вот там, работая над магистерской диссертацией под руководством Ваннивара Буша, он в августе 1937 года, в возрасте двадцати одного года, заканчивает работу, опубликованную год спустя в отраслевом журнале AIEE - и которую многие историки прямо называют самой важной магистерской работой двадцатого века. Психолог Говард Гарднер сформулировал это без всякой скидки на скромность: “возможно, самая важная и при этом самая известная магистерская диссертация века”.
Давайте разберёмся, в чём там дело.
К тридцатым годам телефонные компании использовали сложные системы электромеханических реле для автоматической коммутации звонков - переключающих схем. И эти схемы инженеры проектировали скорее интуитивно, методом проб и ошибок, чем на основе какой-то строгой математической теории.
И вот Шеннон замечает и, что важно, математически строго доказывает одну вещь. Логика булевой алгебры, разработанная английским математиком Джорджем Булем ещё в середине девятнадцатого века для формализации законов человеческого мышления - истина, ложь, И, ИЛИ, НЕ, структурно идентична поведению электрических цепей с переключателями. Ведь каждое реле может быть либо разомкнуто, либо замкнуто. То есть находиться в одном из двух состояний, точно так же, как булева переменная может быть истинной или ложной.
Вдумайтесь, что это означает. Любую логическую функцию, любое сложное логическое выражение можно спроектировать и точно проанализировать как схему из простых переключателей. И, что практически ещё важнее, можно применить строгие математические методы, чтобы минимизировать количество нужных переключателей, вместо того чтобы полагаться на интуицию инженера.
Это и есть тот самый фундаментальный мост между абстрактной логикой, существовавшей до этого лишь как область философии и чистой математики, и физическими электрическими схемами.
Помните арифметико-логическое устройство из архитектуры фон Неймана? Без работы Шеннона это была бы просто красивая схема на бумаге, без объяснения, почему она вообще должна работать на практике.
Каждый логический элемент внутри современного микропроцессора AND, OR, NOT, NAND - это прямая, ничем принципиально не изменившаяся реализация идеи двадцатиодноголетнего студента, доказавшего в 1937 году, что мышление, в булевом, формально-логическом смысле, и переключение тока - это, по сути, одна и та же математика. Просто выраженная в разных материалах.
Часть вторая. Что вообще такое информация
Перематываем на войну и послевоенные годы. Шеннон работает в Bell Labs - компании, чей основной бизнес состоял именно в передаче сигналов на расстояние, в телефонии. И там перед ним встаёт следующая задача - как математически строго определить и измерить количество информации, передаваемой по каналу связи, учитывая неизбежные шум и искажения? И существует ли теоретический предел скорости передачи данных по зашумлённому каналу?
В 1948 году он публикует работу “A Mathematical Theory of Communication” и вот тут происходит вторая радикальная концептуальная инновация в его карьере.
Смотрите, в чём фокус. Шеннон предлагает измерять информацию не через её смысл или ценность - это субъективно, не поддаётся математической формализации, а через степень неожиданности, неопределённости сообщения.
Событие, которое почти наверняка произойдёт, несёт мало информации, когда оно всё-таки происходит мы почти ничего нового не узнаём. А событие маловероятное несёт много информации именно потому, что было неожиданным.
Это позволяет ввести строгую количественную единицу измерения - бит. Кстати, сам термин предложил не Шеннон, а его коллега по Bell Labs Джон Тьюки - как сокращение от “binary digit”. Но именно работа Шеннона закрепила бит как фундаментальную единицу измерения информации на десятилетия вперёд.
И из этого рождается несколько практических следствий, которые лежат в основе всей современной цифровой связи.
Энтропия источника - математическая мера того, сколько в среднем информации несёт сообщение из данного источника. Это задаёт теоретический предел эффективности сжатия данных без потерь. Без этой концепции невозможны ни zip-архивы, ни сжатие изображений и видео.
И пропускная способность канала, Шеннон математически доказывает существование теоретического максимума скорости безошибочной передачи данных по каналу с заданным уровнем шума. И, что особенно поразительно, доказывает, что этого предела можно достичь, пусть не всегда практически, но в принципе, с помощью подходящего кодирования, даже при сколь угодно зашумлённом канале, при условии, что скорость передачи не превышает этот предел.
Каждый раз, когда современный модем, Wi-Fi роутер или мобильная сеть пытается выжать максимум скорости из зашумлённого физического канала - инженеры буквально приближаются к пределу, математически установленному Шенноном в 1948 году. Это не метафора. Это прямое инженерное применение конкретной теоремы, вошедшей в историю как теорема Шеннона-Хартли.
Теория информации Шеннона задаёт математический язык, на котором впервые можно строго говорить о цифровых данных как об абстрактной сущности, полностью отделённой от физического носителя или конкретного смысла сообщения. Число бит, необходимое для кодирования текста, звука, изображения - одинаково поддаётся анализу одними и теми же математическими инструментами.
Часть третья. А теперь самое приятное
Обещанный лёгкий акт.
Шеннон вошёл в историю Bell Labs и MIT не только своими фундаментальными теориями. Он ещё и обожал превращать теоретические идеи в забавные механические демонстрации.
Вот, например, механическая мышь по имени Theseus, 1950 год. Устройство, способное методом проб и ошибок обучаться проходить лабиринт и запоминать успешный путь при повторных попытках. Это ранняя, наглядная демонстрация принципов, которые десятилетия спустя лягут в основу обучения с подкреплением в машинном обучении.
Ещё он строил жонглирующую машину - в частности, механического клоуна ростом почти в метр, жонглирующего мячами наподобие комика У. К. Филдса, известного в том числе своими вставными номерами с жонглированием. Устройство, решающее кубик Рубика. Механический компьютер, играющий в шахматы на упрощённой доске. Кстати, Шеннон одним из первых всерьёз рассматривал теоретические основы компьютерных шахматных программ, есть у него статья на эту тему аж пятидесятого года. Стоит уточнить: собирал он всё это не единовременно, а на протяжении десятилетий, с начала пятидесятых и почти до середины восьмидесятых, сам кубик Рубика, например, физически появился только в 1974-м, так что решающая его машина никак не могла быть ровесницей мыши Theseus.
А ещё он лично увлекался жонглированием, причём одновременно с ездой на одноколёсном велосипеде. И даже опубликовал математическую теорию жонглирования, выведя формулу, связывающую число предметов, высоту бросков и продолжительность нахождения предмета в воздухе против нахождения в руке.
И вот в чём разница с фон Нейманом. Там разносторонность выражалась в параллельной серьёзной работе над оружием и экономикой. А тут это скорее интеллектуальная игра, любопытство ради самого любопытства что делает фигуру Шеннона человечески более лёгкой и симпатичной на фоне более тяжеловесных персонажей нашего цикла.
Итог
Шеннон закрывает сразу два разных, но одинаково фундаментальных концептуальных зазора из прошлых статей.
Во-первых, он объясняет, почему электрическая схема вообще способна реализовывать логику - это тот самый мост между абстрактной булевой алгеброй и физическим железом фон Неймана из прошлого эпизода.
И во-вторых, он даёт строгий математический язык для измерения самой информации - ресурса, о котором будут все последующие темы цикла.
Вопросы, чтобы обсудить в комментариях
Первое - Шеннон сознательно исключил из своей теории вопрос о смысле и ценности сообщения, сосредоточившись только на статистической неопределённости. Насколько это упрощение было необходимым инженерным компромиссом, позволившим построить строгую математическую теорию? И что теряется при таком подходе, если применять его, скажем, к вопросу о том, что вообще значит “значимая” информация в более широком, философском смысле?
Второе - магистерская диссертация как самая влиятельная работа века — что это говорит об академической системе? Насколько редко подобный уровень влияния случается именно на уровне студенческой работы сегодня, в эпоху куда более специализированной и конкурентной академической среды?
И третье, чуть более неожиданное - стоит ли относиться к эксцентричным механическим игрушкам Шеннона не просто как к забавному побочному эффекту его гения, а как к содержательному методу работы? Многие идеи, впоследствии оказавшиеся фундаментальными для машинного обучения, родились именно из желания «поиграть» с идеей, а не из целенаправленного исследовательского плана. Что это говорит про игру как метод познания вообще?
В следующей статье мы наконец перейдём от чистой теории к практическому, массово используемому системному инструментарию. Два человека, одна лаборатория, один заброшенный компьютер и система, которая полвека спустя лежит буквально под интерфейсом каждого смартфона на планете. Это будут Кен Томпсон и Деннис Ритчи — Unix и язык C.
Источники и ссылки по фактам из статьи
Дата рождения Шеннона, детство в Петоски и Гейлорде - Wikipedia: Claude Shannon
Дата подписания диссертации (10 августа 1937 года), возраст на момент завершения работы - патентный документ USPTO со ссылкой на оригинал рукописи, CASBS Stanford: очерк о Шенноне
Цитата Говарда Гарднера о диссертации как “самой важной и самой известной работе века” - MIT Alumni Association: Claude Shannon
Термин “бит” предложен Джоном Тьюки - упомянуто в ряде источников об истории теории информации, см. общий обзор в Wikipedia: Claude Shannon
Коллекция механических устройств Шеннона (мышь Theseus, жонглирующий У. К. Филдс и другие), переданная в музей MIT, включая хронологию “с 1950-х по середину 1980-х” - MIT News: Shannon collection shows wit and whimsy
Год изобретения кубика Рубика (1974) - общеизвестный факт, не отдельно подтверждаемый источник
Дополнительное чтение к данной статье
Клод Шеннон - “A Symbolic Analysis of Relay and Switching Circuits” (1937, опубликована в 1938 году) Оригинальная магистерская диссертация. Технически плотная, но короткая. Для тех, кто хочет увидеть саму идею соединения булевой алгебры и электрических цепей в первозданном виде.
Клод Шеннон - “A Mathematical Theory of Communication” (1948, опубликована в Bell System Technical Journal) Доступна в открытом доступе на сайте Bell Labs и в академических архивах. Читается тяжелее диссертации, но при желании можно ограничиться первыми разделами про энтропию, не углубляясь в математический аппарат целиком.
Джимми Соуни, Ронг Гудман - “A Mind at Play: How Claude Shannon Invented the Information Age” (2017) Пожалуй, лучшая биография Шеннона из существующих. Живо написанная, охватывает и техническую часть, и эксцентричные увлечения из третьей части эпизода. Если читать одну книгу про Шеннона, то эту.
Джеймс Глик - “Информация. История. Теория. Поток” (в оригинале “The Information: A History, a Theory, a Flood”, 2011, есть перевод на русский) Книга про историю самого понятия информации в целом, не только про Шеннона. Хорошо показывает интеллектуальный контекст, в который вписывается его работа.
Клод Шеннон - “Programming a Computer for Playing Chess” (1950) Для желающих подробнее раскрыть тему компьютерных шахмат.
OldCreater
А что вы скажете о теореме Котельникова?