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

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

— Клод Шеннон

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

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

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

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

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

Энтропия#

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

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

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

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

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

Природа «открыла» избыточность за миллиарды лет до Шеннона. В генетическом коде шестьдесят четыре тройки «букв» кодируют всего двадцать аминокислот, и многие аминокислоты записываются несколькими разными тройками. Поэтому многие случайные замены одной буквы ничего не меняют в белке: ошибка гасится раньше, чем успевает навредить.

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

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

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

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

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

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

Код#

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

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

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

Алгоритмы#

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

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

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

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

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

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

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

Сеть#

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

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

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