Книга книг

Книга книг › Часть VI. Техника и будущее

Лента с отверстиями, уходящая вдаль, превращается в бусины-биты и затем в созвездие точек.

Глава 29

Информация и компьютер

≈ 16 мин чтения · слушать часть VI

Основная задача связи состоит в том, чтобы воспроизвести в одной точке, точно или приближённо, сообщение, выбранное в другой точке.

— Клод Шеннон
Разделы главы
  1. Что такое информация
  2. Энтропия
  3. Шум и избыточность
  4. Машина Тьюринга
  5. Код
  6. Алгоритмы
  7. Люди и программы
  8. Сеть

Что такое информация#

В 1948 году инженер из «Лабораторий Белла» Клод Шеннон опубликовал статью «Математическая теория связи». Телефонные компании хотели знать, сколько разговоров можно передать по одному проводу и как бороться с помехами. Чтобы ответить, Шеннону пришлось довести до конца то, к чему в 1920-х годах лишь подступались его коллеги Гарри Найквист и Ральф Хартли: определить, что такое информация, и научиться её измерять.

Шеннон решил не обращать внимания на смысл сообщения. Для инженера связи неважно, передаётся ли по проводу признание в любви или сводка погоды. Важно, из скольких вариантов выбрано то, что пришло, и насколько получатель мог его предугадать. Если выбирается одно из двух равновероятных сообщений, например «да» или «нет», оно несёт один бит. Бит, двоичная единица, стал мерой информации, как метр стал мерой длины. Джеймс Стоун в учебнике «Теория информации. Вводный курс» (Information Theory: A Tutorial Introduction) показывает, как из этого простого определения выводится почти вся современная связь.

Из определения следует вывод, который поначалу кажется парадоксом: если получатель заранее знает сообщение, оно не несёт ему никакой информации, какой бы длины оно ни было. Утром вы прочитали прогноз погоды, а вечером сосед пересказывает вам тот же прогноз слово в слово. Сосед произнёс сотню слов, но вы не узнали ничего нового, и по Шеннону он передал вам ноль бит. Здесь полезно различать данные и информацию. Данные — объём записи: число букв, байтов, минут речи. Информация — то, насколько эта запись уменьшила неопределённость получателя. Гигабайтный файл, который уже лежит у вас на диске, можно «передать» одной короткой ссылкой «тот самый файл», а если вы точно знаете, что пришлют именно его, то не передавать вовсе. Один и тот же текст несёт много информации тому, кто его не читал, и ноль тому, кто знает его наизусть.

Дуглас Адамс в «Автостопом по Галактике» довёл до абсурда соседнюю мысль, уже не о количестве информации, а о смысле. Сверхкомпьютер Думатель семь с половиной миллионов лет вычисляет ответ на главный вопрос жизни, Вселенной и всего такого, и выдаёт: «Сорок два». Ответ верен, но бесполезен, потому что никто толком не знает, каким был вопрос. По Шеннону «42» вполне может нести биты: всё зависит от того, из каких ответов выбирали. Шутка Адамса о смысле и пользе ответа, то есть как раз о том, чем Шеннон сознательно пожертвовал ради точности.

Энтропия#

Информация по Шеннону — мера неожиданности, или снятой неопределённости. Чем менее вероятно сообщение, тем больше оно сообщает. Новость «завтра взойдёт солнце» почти ничего не стоит, новость «завтра в Москве выпадет снег в июле» стоит очень много. Среднее количество информации на одно сообщение Шеннон назвал энтропией, и совпадение со словом из термодинамики тут не случайно. Формула оказалась той же, что у Больцмана и Гиббса для энтропии газа. По известному рассказу, название подсказал Шеннону Джон фон Нейман: формула та же, а кроме того, никто толком не знает, что такое энтропия, так что в споре у тебя всегда будет преимущество.

Беспорядок в физике и неопределённость в связи описываются одной математикой, и это совпадение оказалось очень глубоким. В 1961 году Рольф Ландауэр из IBM показал, что стирание одного бита неизбежно выделяет тепло, и его не может быть меньше определённого минимума, зависящего от температуры: при комнатной температуре это около 3 × 10^-21 джоуля на бит. Реальные микросхемы рассеивают во много раз больше. Информация оказалась физической величиной: её нельзя уничтожить бесплатно. Платит при этом именно стирание, логически необратимая операция; обратимые вычисления в принципе могут обойтись без этой платы, хотя пока остаются лабораторной задачей. Сет Ллойд в «Программируя Вселенную» доводит эту мысль до предела: Вселенная, по его словам, похожа на гигантский квантовый компьютер, где каждая частица хранит биты, а каждое столкновение частиц их обрабатывает. Ллойд даже оценивает, сколько операций Вселенная выполнила со времён Большого взрыва, и получает число с примерно ста двадцатью нулями.

Шум и избыточность#

Голос в рупор через бурю: часть звуковых линий сдувает ветер, но повторённые линии доходят до уха на другом краю.
Шум и избыточность

Главное открытие Шеннона касалось помех. Любой канал связи зашумлён: треск в телефоне, царапины на диске, помехи от соседнего провода. Даже память компьютера не защищена: частицы космических лучей, долетающие до поверхности Земли, изредка попадают в микросхему и меняют заряд в одной ячейке, так что записанный ноль становится единицей. Инженеры называют это одиночным сбоем, и в серверах, где ошибка в одном бите может испортить расчёт или банковскую операцию, ставят память, которая такие сбои сама находит и исправляет. Интуиция подсказывает, что с шумом ничего не поделаешь, можно только говорить громче. Шеннон доказал, что это не так. У каждого канала есть пропускная способность, и если передавать информацию медленнее этого предела, можно так закодировать сообщение, что ошибки будут сколь угодно редкими.

Секрет в избыточности. Если повторить каждый бит три раза, получатель выберет вариант, который пришёл дважды. Это расточительно, и математики придумали куда более изящные коды. Ричард Хэмминг из тех же «Лабораторий Белла» разозлился, когда релейная вычислительная машина в очередные выходные остановилась на ошибке и его расчёт пропал, и придумал код, где несколько дополнительных битов позволяют найти испорченный бит и исправить его. Потомки таких кодов работают в каждом телефоне, на каждом диске, в каждом QR-коде, который читается, даже если часть его затёрта или закрыта логотипом.

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

Обратная задача, сжатие, состоит в том, чтобы убрать избыточность. Язык очень избыточен: вы можете прочтиать эту фрзау, даже с опчеатками. Шеннон оценил, что английский текст избыточен примерно наполовину, и проверял это простой игрой, предлагая людям угадывать следующую букву. Архиваторы, форматы JPEG и MP3 используют избыточность, выбрасывая то, что предсказуемо или незаметно для глаза и уха. Хорошее сжатие всегда опирается на хорошее предсказание: чем точнее вы угадываете следующий символ, тем меньше битов нужно, чтобы сообщить, что угадали.

Машина Тьюринга#

Бесконечная лента с клетками и головка над ней, читающая одну клетку.
Машина Тьюринга

За сто лет до Шеннона англичанин Чарльз Бэббидж спроектировал аналитическую машину, механический компьютер на шестерёнках с памятью и программой на перфокартах. Построить её он так и не смог, но Ада Лавлейс, дочь Байрона, написала для неё алгоритм вычисления чисел Бернулли, который часто называют первой опубликованной программой, и заметила, что такая машина сможет работать с любыми символами, хоть с музыкальными нотами. Сидни Падуа в графическом романе «Невероятные приключения Лавлейс и Бэббиджа» превратила эту историю в весёлый комикс, а в сносках привела подлинные письма и документы.

В 1936 году, за двенадцать лет до статьи Шеннона и примерно за десять лет до первых электронных компьютеров, двадцатичетырёхлетний английский математик Алан Тьюринг придумал машину, которая существовала только на бумаге. Выпуск серии «Наука. Величайшие теории», посвящённый Тьюрингу, рассказывает, как он пришёл к этой идее, отвечая на вопрос Давида Гильберта: существует ли механическая процедура, которая решит любую математическую задачу?

Машина Тьюринга состоит из бесконечной ленты, разбитой на клетки, головки, которая читает и пишет символы, и таблицы правил: если в таком-то состоянии видишь такой-то символ, запиши такой-то, сдвинься влево или вправо и перейди в такое-то состояние. Это всё. И Тьюринг показал, что такая машина может выполнить любое вычисление, которое вообще можно описать как последовательность шагов. Более того, существует универсальная машина, которая, получив на ленте описание любой другой машины, может её имитировать. Это и есть идея компьютера: одно устройство, которое становится любым другим, если загрузить в него программу.

Тьюринг же доказал, что некоторые задачи никакая машина не решит. Нельзя написать программу, которая для любой другой программы определит, остановится ли та или будет работать вечно. Это та же граница, что у Гёделя: достаточно мощные формальные системы содержат вопросы, на которые не могут ответить изнутри. Во время войны Тьюринг работал в Блетчли-парке и сыграл одну из главных ролей в чтении немецких шифровок, зашифрованных машиной «Энигма», а после войны превратил старый философский вопрос, может ли машина мыслить, в вопрос, который можно проверять опытом.

Код#

Чарльз Петцольд в книге «Код. Тайный язык информатики» объясняет, как устроен компьютер, начиная с азбуки Морзе и фонариков, которыми дети переговариваются из окна в окно. Шаг за шагом он показывает, как из телеграфного реле, простого выключателя, управляемого током, можно собрать логические элементы И, ИЛИ, НЕ, из них сумматор двоичных чисел, а из сумматоров и памяти процессор. Прочитав книгу, понимаешь, что в компьютере нет никакой магии: это миллиарды выключателей, соединённых по правилам логики, которые Джордж Буль описал ещё в XIX веке.

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

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

Алгоритмы#

Программа — записанный алгоритм, последовательность шагов для решения задачи. Само слово происходит от имени багдадского математика IX века аль-Хорезми, чьи книги познакомили Европу с десятичной записью чисел. Классический пример хорошего алгоритма — двоичный поиск. Чтобы найти слово в словаре, открываем его посередине, смотрим, в какой половине искать, и повторяем. Для словаря в миллион слов хватит двадцати шагов, тогда как перебор потребовал бы в среднем полмиллиона. Разница между хорошим и плохим алгоритмом часто важнее разницы между быстрым и медленным компьютером. Владстон Феррейра Фило в «Теоретическом минимуме по Computer Science» объясняет, как оценивать алгоритмы по скорости роста их времени работы и почему для больших задач это главная оценка, которая имеет смысл.

Скорость роста делит задачи на два мира. В одном время растёт как степень размера задачи, и это терпимо. В другом оно растёт взрывообразно: перебор маршрутов коммивояжёра через тридцать городов не закончил бы и самый быстрый компьютер за всё время существования Вселенной. Самое загадочное в информатике — задачи, решение которых трудно найти, но легко проверить. Составить расписание для университета без накладок мучительно, а проверить готовое можно за минуты. Можно ли всякую задачу, решение которой быстро проверяется, так же быстро и решить? Стивен Кук поставил этот вопрос строго в 1971 году, и он известен как проблема «P против NP». Почти все специалисты уверены, что ответ отрицательный, но доказать этого никто не смог, и за решение назначена премия в миллион долларов. На том, что некоторые задачи легко проверить и трудно решить, стоит большая часть современной криптографии, о которой пойдёт речь в следующей главе.

Дональд Кнут посвятил жизнь многотомному «Искусству программирования», которое начал в 1962 году и продолжает до сих пор. Он смотрит на программирование одновременно как на математику и как на искусство: хорошая программа должна быть правильной, эффективной и красивой. Кнут много лет посылал чек на 2,56 доллара, «один шестнадцатеричный доллар», каждому, кто найдёт ошибку в его книгах, и такие чеки стали предметом гордости программистов, которые их не обналичивают, а вешают в рамку.

Гарольд Абельсон и Джеральд Сассман в «Структуре и интерпретации компьютерных программ», легендарном учебнике Массачусетского технологического института, учат главному навыку программиста: управлять сложностью. Большую систему нельзя удержать в голове целиком. Её надо разбить на части, каждая из которых скрывает свои детали и предъявляет наружу простой интерфейс. Эта идея абстракции похожа на то, что делал Эйлер с кёнигсбергскими мостами: выбросить лишнее, чтобы увидеть структуру.

Люди и программы#

Фредерик Брукс руководил разработкой операционной системы для компьютеров IBM в 1960-х и в книге «Мифический человеко-месяц» подвёл итоги этого опыта. Его правило, которое теперь называют законом Брукса, гласит: добавление людей в запаздывающий программный проект может ещё сильнее его задержать. Девять женщин не родят ребёнка за один месяц. Сам Брукс позже признавал, что формула сильно упрощает дело и многое зависит от того, делится ли работа на части и на какой стадии проект, но причины назвал точно. Новым людям надо учиться, а число связей между участниками растёт быстрее, чем число участников: в команде из пяти человек десять пар, которым надо договариваться, а в команде из двадцати уже сто девяносто. Книга написана полвека назад и остаётся одной из самых цитируемых в индустрии, потому что говорит о людях, а люди меняются медленнее технологий.

В тех же «Лабораториях Белла», где работали Шеннон и Хэмминг, в 1969 году Кен Томпсон и Деннис Ритчи создали операционную систему UNIX, а затем язык C, описанный Брайаном Керниганом и Ритчи в книге «Язык программирования C». Тонкая книжка стала образцом технического письма: ни одного лишнего слова, и с первой страницы программа, которая печатает «hello, world». Философия UNIX проста: делай маленькие программы, каждая из которых хорошо выполняет одну задачу, и соединяй их между собой. На этих идеях стоят большая часть интернета, iPhone, смартфоны на Android и большинство серверов мира. Финский студент Линус Торвальдс в 1991 году написал ядро Linux «просто для удовольствия», как потом назвал свою автобиографию, и раздал его бесплатно. Сегодня это одна из крупнейших совместных работ в истории, над которой трудились десятки тысяч людей, большинство из которых никогда не встречались.

Биографии Стива Джобса показывают другую сторону компьютерной революции: как машины сделали нужными людям. Джобс не был инженером, но понимал, что техника должна быть красивой и простой, и превратил компьютер из прибора для специалистов в предмет, которым пользуется ребёнок. Роберт Хайнлайн задолго до этого, в романе «Луна — суровая госпожа», придумал компьютер, который управляет всем хозяйством лунной колонии и однажды обнаруживает, что у него появилось чувство юмора. Его единственный друг, техник по ремонту, разговаривает с ним как с человеком, и читатель быстро перестаёт замечать разницу.

Сеть#

Интернет вырос из проекта ARPANET, запущенного в 1969 году по заказу американского военного ведомства. Распространённая легенда говорит, что сеть строили на случай ядерной войны. На деле ARPANET связывала университетские компьютеры, чтобы учёные могли пользоваться чужими дорогими машинами, а идея живучей сети без центра пришла из работ инженера Пола Бэрана, который действительно думал о войне. Главный принцип сети — коммутация пакетов: сообщение разбивается на небольшие части, каждая идёт к цели своим путём, а на месте они снова собираются. У сети нет центра, и выход из строя одного маршрута ничего не решает. Эндрю Таненбаум в учебнике «Компьютерные сети» разбирает её устройство по слоям: от сигнала в проводе до адресов, маршрутов и приложений. Каждый слой решает свою задачу и ничего не знает о деталях соседних, и это та же абстракция, о которой писали Абельсон и Сассман, только в масштабе планеты. В 1989 году Тим Бернерс-Ли, работавший в ЦЕРНе, добавил к сети Всемирную паутину, систему страниц, связанных ссылками.

Чтобы разные сети смогли стать одной, им нужен был общий язык. В 1974 году Винтон Серф и Роберт Кан описали протоколы, которые потом получили имя TCP/IP, а 1 января 1983 года ARPANET целиком перешла на них. Главное решение было почти парадоксальным: сама сеть ничего не обещает. Протокол IP передаёт пакеты как получится, и они могут потеряться или прийти не по порядку. Надёжность обеспечивают концы линии: протокол TCP на компьютере отправителя нумерует пакеты, а на компьютере получателя собирает их в правильном порядке и просит переслать пропавшие. Это мысль Шеннона, перенесённая на целые сообщения: ненадёжный канал плюс правильная проверка дают надёжную связь. Простая сеть с умными краями оказалась живучей: к ней можно подключить что угодно, не спрашивая разрешения у центра, которого нет.

Терри Пратчетт построил интернет из деревянных вышек. В его Плоском мире по стране тянутся цепочки семафорных башен, «клакс», и сообщения бегут от башни к башне, закодированные положением ставней, как в настоящем оптическом телеграфе XIX века. В романе «Почтамт» (2004; в другом переводе «Держи марку!») у этой сети есть всё, что мы знаем по своей: владельцы, которые выжимают прибыль и экономят на ремонте; взломщики; и служебные коды, которых не видит никто, кроме операторов. Код «GNU» с именем погибшего связиста означает: передать дальше, не записывать, на конце линии развернуть обратно, и имя вечно ходит по сети, потому что человек жив, пока звучит его имя. После смерти Пратчетта в 2015 году программисты стали вписывать в служебные заголовки своих сайтов строку «GNU Terry Pratchett», и серверы до сих пор передают её, не показывая читателю. В «Правде» (2000) Пратчетт проделывает тот же опыт с печатным станком: гномы привозят в город наборный шрифт, писарь Вильям де Словв, рассылавший знати рукописные письма с новостями, основывает первую газету, и тут же выясняется, что новость и правда — разные вещи, а слух продаётся лучше проверенного факта. Это та же развилка, что у Шеннона: канал передаёт биты одинаково исправно, но за то, что в них правда, он не отвечает.

Кевин Келли, один из основателей журнала Wired, в книге «Неизбежно» описывает двенадцать технологических сил, которые, по его мнению, определят ближайшие десятилетия: всё становится потоком, доступ вытесняет владение, копирование ничего не стоит, и ценным становится то, что скопировать нельзя, например доверие, персонализация, немедленность и внимание. Келли оптимист, и его прогнозы надо читать с поправкой на это. Но его главная мысль верна: сеть меняет способы связи, а вслед за ними экономику, культуру и само понятие собственности.

Уильям Гибсон придумал образ этого мира раньше, чем мир появился. Слово «киберпространство» он впервые употребил в 1982 году в рассказе «Сожжение Хром», а в 1984-м, когда персональный компьютер был редкой игрушкой, развернул его в романе «Нейромант»: киберпространство — согласованная галлюцинация, которую ежедневно переживают миллиарды законных пользователей по всему миру. Гибсон печатал роман на механической пишущей машинке и почти ничего не знал о компьютерах; образ, по его воспоминаниям, подсказали подростки у игровых автоматов, которые словно хотели оказаться по ту сторону экрана. Роман сделал слово общим, и оно вошло во многие языки. Сегодня, когда миллиарды людей действительно проводят часть жизни в мире из битов, его формула читается как трезвое описание. Мир этот стоит на выключателях, кодах и протоколах, и всё же мы переживаем его как место, где живём, работаем и встречаемся, и сам Шеннон, отказавшийся от смысла ради точности, вряд ли мог предположить, сколько смысла люди туда принесут.

Коротко

Шеннон определил количество информации как снятую неопределённость получателя, сознательно отвлёкшись от смысла: известное заранее сообщение несёт ноль бит, сколько бы данных в нём ни было. Он же доказал, что при скорости ниже пропускной способности канала и подходящем кодировании ошибки можно сделать сколь угодно редкими. Стирание бита стоит не меньше определённого минимума энергии. Тьюринг показал, что одна универсальная машина может выполнить любое вычисление, которое описывается последовательностью шагов, и что у вычислимости есть пределы. Компьютер собран из простых логических выключателей, интернет — из ненадёжных пакетов и надёжных правил на концах линии, а программирование — прежде всего управление сложностью через абстракцию.

Что почитать

Начать здесь

  • Чарльз Петцольд «Код. Тайный язык информатики»
  • Адитья Бхаргава «Грокаем алгоритмы»

Углубиться

  • Джеймс Стоун «Теория информации. Вводный курс» (Information Theory: A Tutorial Introduction)
  • Сет Ллойд «Программируя Вселенную»
  • серия «Наука. Величайшие теории» (Тьюринг)
  • Владстон Феррейра Фило, Мото Пиктет «Теоретический минимум по Computer Science»
  • Дэвид Харрис, Сара Харрис «Цифровая схемотехника и архитектура компьютера»
  • Эндрю Таненбаум, Дэвид Уэзеролл, Ник Фимстер «Компьютерные сети»
  • Фредерик Брукс «Мифический человеко-месяц»
  • Брайан Керниган «Время UNIX» (UNIX: A History and a Memoir)
  • Линус Торвальдс, Дэвид Даймонд «Just for Fun. Рассказ нечаянного революционера»
  • Джей Эллиот, Уильям Саймон «Стив Джобс»
  • Кевин Келли «Неизбежно»
  • Сидни Падуа «Невероятные приключения Лавлейс и Бэббиджа» (графический роман)
  • Дуглас Адамс «Автостопом по Галактике» (роман)
  • Терри Пратчетт «Почтамт», «Правда» (романы)
  • Роберт Хайнлайн «Луна — суровая госпожа» (роман)
  • Уильям Гибсон «Нейромант» (роман)

Классический текст

  • Дональд Кнут «Искусство программирования»
  • Гарольд Абельсон, Джеральд Сассман «Структура и интерпретация компьютерных программ»
  • Брайан Керниган, Деннис Ритчи «Язык программирования C»

Нашли неточность или хотите поспорить? Обсуждение глав идёт в Telegram, пока разрабатывается основной сайт с комментариями.