Книга: Информация. История. Теория. Поток
Назад: Глава 11. В МЕМОФОНД. Вы паразитируете на моем мозге
Дальше: Глава 13. ИНФОРМАЦИЯ КАК ФИЗИЧЕСКАЯ ВЕЛИЧИНА. Все из бита
Глава 12. СМЫСЛ СЛУЧАЙНОСТИ. Согрешившие
“Любопытно, — сказала она. — В последнее время все труднее различать закономерности, тебе так не кажется?“Майкл Каннингем (2005)
В 1958 году Грегори Хайтин, не по годам развитой одиннадцатилетний сын живущих в Нью-Йорке иммигрантов из Аргентины, нашел в библиотеке маленькую волшебную книжку и некоторое время носил ее с собой, пытаясь объяснить содержание другим детям, а потом, признавался он, попытался понять ее сам. Это было “Доказательство Геделя” Эрнста Нагеля и Джеймса Р. Ньюмана. В выросшей из статьи в Scientific American книге описывалось возрождение логики, начавшееся с Джорджа Буля; процесс записи, кодирования утверждений о математике с помощью символов и даже целых чисел; идея метаматематики, систематизированного языка о математике и, следовательно, выходящего за пределы математики. Это были темы, трудные для понимания мальчика, который последовал за авторами по пути упрощенного, но строгого описания “удивительной и меланхоличной” демонстрации Геделем того, что формальная математика никогда не сможет быть свободной от противоречий.
Огромную часть практической математики, существовавшей в то время, совершенно не волновало доказательство Геделя. Как бы ни был поразителен факт неполноты, он казался некоторым образом случайным, ничего не привносившим в полезную работу математиков, которые продолжали делать открытия и доказывать теоремы. Но философски настроенные души были глубоко обеспокоены этим доказательством, и именно к их числу принадлежали люди, работы которых так любил изучать Хайтин. Одним из этих обеспокоенных был Джон фон Нейман — он узнал о доказательстве Геделя еще в 1930 году, в Кенигсберге, а затем в США сыграл ведущую роль в разработке вычислительной техники и теории вычислений. Для Неймана доказательство Геделя стало точкой невозврата.
Это был очень серьезный концептуальный кризис в области строгости и надлежащих способов давать корректные математические доказательства. С точки зрения более ранних понятий абсолютной математической строгости удивительно, что такая вещь вообще могла появиться, и еще удивительнее то, что она смогла появиться в дни, когда чудеса уже не должны были случаться. Но она появилась.
Почему? Этот вопрос волновал Хайтина. Ему было интересно, нельзя ли на каком-то уровне связать неполноту Геделя с новым принципом квантовой физики, принципом неопределенности, который почему-то казался очень похожим. Позже уже у взрослого Хайтина была возможность задать этот вопрос Джону Арчибальду Уилеру. Была ли неполнота Геделя связана с неопределенностью Гейзенберга? Уилер сказал, что сам однажды задал этот вопрос Геделю в его кабинете Института перспективных исследований, где тот сидел, укрыв от зимних сквозняков ноги пледом и с включенным на полную мощность электрическим обогревателем. Гедель отказался отвечать. Таким образом, рассказав эту историю, Уилер в свою очередь отказался отвечать Хайтину.
Когда Хайтин наткнулся на доказательство невычислимости Тьюринга, он решил, что это и есть ключ. Он нашел также книгу Шеннона и Вивера “Математическая теория связи” и был поражен ее новым определением энтропии, словно перевернутым с ног на голову: с одной стороны — энтропия битов, измеряющая информацию, с другой — беспорядок. Общим элементом была случайность, неожиданно подумал Хайтин. Шеннон ошибался, связав случайность с информацией. Физики обнаружили случайность внутри атома — тот вид случайности, на который жаловался Альберт Эйнштейн, когда сказал о Боге и игральных костях. Все эти герои науки говорили о случайности или о чем-то на нее похожем.
Все знают, что значит простое слово “случайный”. Все и никто. Философы и математики вели бесконечную борьбу. Уилер говорил: “Вероятность, как и время, есть понятие, придуманное людьми, и людям придется нести ответственность за неясность, которая в нем присутствует”. Результат подбрасывания “правильной” симметричной монеты случаен, хотя каждый фрагмент траектории монеты может быть определен по Ньютону. Является ли численность населения Франции четным или нечетным числом в любой выбранный момент времени — случайное событие, но сама численность населения Франции определенно не случайна: это точный факт, даже если его нельзя узнать. Джон Мейнард Кейнс пытался найти решение для случайности в терминах, обратных ей, и он выбрал три: знание, причинность и структура. То, что известно заранее, определено причиной или организовано в соответствии с планом, не может быть случайным.
“Случай — это лишь мера нашего неведения, — сказал Анри Пуанкаре. — Феноменами случайности являются по определению те, законы которых мы не знаем”. И немедленно отрекся: “Удовлетворительно ли такое определение? Когда первые халдейские пастухи смотрели на движение звезд, они еще не знали законов астрономии, но могли ли они помыслить о том, чтобы назвать движение звезд случайным?” Для Пуанкаре, который понял хаос задолго до того, как тот стал наукой, примерами случайности были такие феномены, как место падения капли дождя, причины которого физически определены, но настолько многочисленны и сложны, что их можно считать неопределенными. В физике или любом природном процессе, который кажется непредсказуемым, явная случайность способна быть шумом или может быть порождена сложной глубинной динамикой.
Незнание субъективно. Это качество наблюдателя. Случайность, если она вообще существует, предположительно должна быть свойством самой вещи. Исключив из рассмотрения людей, хотелось бы иметь возможность сказать, что событие, выбор, распределение, игра или, проще всего, число является случайным.
Понятие случайного числа полно сложностей. Может ли существовать такая вещь, как особое случайное число? Конкретное случайное число? Это число, вероятно, случайно:
10097325337652013586346735487680959091173929274945...
С другой стороны, оно особенное. С него начинается книга под названием “Миллион случайных чисел”, опубликованная в 1955 году. Корпорация RAND получила эти числа с помощью машины, которую описывала как электронную рулетку, — генератора импульсов: 100 тыс. импульсов в секунду пропущены через пятиразрядный двоичный счетчик, затем через преобразователь из двоичной системы в десятеричную, переданы на перфоратор IBM и напечатаны с помощью IBM модели 856 Cardatype. Процесс занял годы. Когда первая порция чисел была проверена, статистики обнаружили значительные отклонения — знаки, группы знаков или структуры знаков, которые появлялись слишком часто или недостаточно часто. Тем не менее таблицы были опубликованы. “Исходя из самой природы таблиц, — сухо заявили редакторы, — мы не посчитали необходимым вычитывать каждую страницу окончательной рукописи, чтобы выявить случайные ошибки Cardatype”.
Книга продавалась, потому что ученым нужны были случайные числа в большом количестве, чтобы использовать их в разработке статистически честных экспериментов и создании реалистичных моделей сложных систем. Новый метод симуляции Монте-Карло для моделирования феноменов, не поддающихся аналитическим решениям, включал в себя случайную выборку. Симуляция Монте-Карло была придумана и названа в рамках проекта создания атомной бомбы командой фон Неймана, отчаянно пытавшейся сгенерировать случайные числа для расчета диффузии нейтронов. Фон Нейман понимал, что механическая вычислительная машина с ее детерминированными алгоритмами и конечным объемом памяти никогда не сможет сгенерировать по-настоящему случайные числа. Ему придется довольствоваться псевдослучайными — детерминированно вычисленными числами, которые вели себя так, будто были случайными. Они были достаточно случайны для практических целей. “Любой, кто раздумывает над арифметическими методами получения случайных чисел, вне сомнения, совершает грех”, — сказал фон Нейман.
Случайность можно определить в терминах порядка, то есть его отсутствия. Это упорядоченное маленькое число вряд ли можно назвать “случайным”:
00000.
Тем не менее оно эпизодически встречается посреди знаменитого миллиона случайных знаков. В терминах вероятности этого надо было ожидать: ооооо — настолько же вероятное число, как и любая из 99,999 возможных пятизначных строк. Где-нибудь еще среди миллиона случайных знаков мы найдем
010101.
Оно тоже кажется упорядоченным.
Чтобы выделить регулярные фрагменты в этих джунглях знаков, требуется проделать работу, на которую способен только разумный наблюдатель. При достаточно длинной цепочке случайных знаков каждый возможный фрагмент короткой строки где-то появится. Один из фрагментов будет комбинацией замка банковского хранилища. Другой окажется зашифрованным полным собранием сочинений Шекспира. Но они никому не пригодятся, потому что никто не сможет их найти.
Вероятно, стоит говорить о том, что числа вроде 00000 и 010101 могут быть случайными в определенном контексте. Если кто-то достаточно долго подбрасывает “правильную” монету (один из простейших генераторов случайных чисел), в какой-то момент монета обязательно упадет орлом вверх десять раз подряд. Когда это случится, желающий получить случайные числа проигнорирует результат и пойдет выпить кофе. Это одна из причин того, почему у людей плохо получается генерировать случайные числа даже с механической помощью. Исследователи установили, что интуиция человека бесполезна как в предсказании случайностей, так и в их распознавании. Люди волей-неволей склоняются к упорядоченности. Публичная библиотека Нью-Йорка купила “Миллион случайных чисел” и поставила ее в разделе психологии. В 2010 году ее все еще можно было купить на Amazon за 81 доллар.
Число (как мы теперь понимаем) есть информация. Когда современные люди, наследники Шеннона, думают об информации в ее наивысшей, чистой форме, они могут представить себе строку из нулей и единиц, двоичное число. Вот два двоичных числа по пятьдесят знаков каждое:
Если Алиса (А) и Боб (Б) говорят, что сгенерировали свои строки, подбрасывая монету, никто никогда не поверит Алисе. Строки, без всяких сомнений, не одинаково случайны. Классическая теория вероятности не дает никаких оснований считать, что строка Б более случайна, чем строка А, потому что случайный процесс может дать любую из строк. Вероятность говорит о множествах, а не об отдельных событиях. Теория вероятности рассматривает события статистически. Она не любит вопросов в форме “насколько вероятно, что это случится?”. Что случилось, то случилось.
Шеннон рассматривал бы эти строки как сообщения. Он спросил бы: “Сколько информации содержит каждая из строк?” На первый взгляд обе содержат 50 бит. Оператор телеграфа, берущий фиксированную тарифную ставку за знак, измерил бы длину сообщений и попросил бы у Алисы и у Боба одинаковую сумму. Но сообщения очень непохожи друг на друга. Сообщение А сразу кажется скучным: как только вы распознали закономерность, дальнейшие повторения не несут новой информации. В сообщении Б ценен каждый бит. Первая шенноновская формулировка теории информации рассматривала сообщения статистически как выбор из множества всех возможных сообщений, в случае сообщений А и Б — из 250 сообщений. Но Шеннон также учитывал избыточность внутри сообщения: регулярность, структуру, порядок, который позволяет сжимать сообщения. Чем больше регулярности в сообщении, тем более оно предсказуемо. Чем более предсказуемо, тем более избыточно. Чем более избыточно сообщение, тем меньше информации в нем содержится.
У оператора телеграфа, посылающего сообщение А, есть способ упростить работу: он может передать что-нибудь вроде “Повторить “01” двадцать пять раз”. Для длинных сообщений с простыми закономерностями экономия нажатий на клавиши становится огромной. Как только понята закономерность, дополнительные знаки бесплатны. Оператор, передающий сообщение Б, — это солдат, выбравший трудный путь; ему придется передать каждый знак, потому что каждый знак в этом сообщении абсолютно непредсказуем; каждый знак несет один бит информации. Эта пара вопросов — насколько случайно и как много информации — оказывается одним и тем же вопросом. С одним ответом.
Хайтин не думал о телеграфе. Он не мог выбросить из головы другое устройство, машину Тьюринга — невыносимо элегантную абстракцию, шагающую туда-сюда по своей бесконечной бумажной ленте, читающую и пишущую символы. Свободная от беспорядка реального мира, от скрипящих шестеренок и привередливого электричества, освобожденная от любой жажды скорости, машина Тьюринга была идеальным компьютером.
Фон Нейман тоже постоянно возвращался к машинам Тьюринга. Они были лабораторными мышами теории вычислительных машин, они были всегда под рукой, U-машина Тьюринга обладает исключительной мощностью: она способна симулировать любой другой цифровой компьютер, поэтому ученые могут пренебречь нагромождением подробностей какой-либо отдельной марки или модели. Это освобождает.
Клод Шеннон, перейдя из Лабораторий Белла в МТИ, еще раз проанализировал машину Тьюринга в 1956 году. Он выбросил из нее все, оставив только основу, доказав, что универсальный компьютер может быть сконструирован таким образом, что будет иметь только два возможных внутренних состояния, или два символа — 0 и 1, или пробел и не пробел. Он записал свое доказательство в более прагматичных, чем математические, терминах. Он в точности описал, как машина Тьюринга с двумя состояниями шагала бы вправо и влево, “раскачиваясь” для того, чтобы помнить большее число состояний в более сложном компьютере. Все это было очень сложно и специфично и наталкивало на мысли о Бэббидже. Например,
когда считывающая головка перемещается, информацию о состоянии необходимо перенести в следующий квадрат ленты, используя всего два внутренних состояния машины Б. Пусть, например, следующим состоянием машины А должно быть состояние 17 (согласно какой-нибудь системе счисления). Чтобы перенести его символ, считывающая головка “качается” вперед и назад между старым и новым квадратом 17 раз (точнее, 18 раз в новый квадрат и 17 назад в старый).
Операция “качания” переносит информацию от ячейки к ячейке, а ячейки действуют как “передатчики” и “контроллеры”.
Тьюринг назвал свою великую статью “О вычислимых числах”, но, конечно, его внимание на самом деле было посвящено не вычислимым числам. Могут ли быть связаны невычислимые и случайные числа? В 1965 году Хайтин был студентом нью-йоркского Сити-колледжа и писал статью, которую надеялся опубликовать в журнале, это была бы его первая публикация. Он начал: “В этой статье машина Тьюринга рассматривается как неспециализированная вычислительная машина и задаются некоторые практические вопросы относительно ее программирования”.
Хайтин, будучи старшеклассником, участвовал в программе Колумбийского университета для школьников, интересующихся наукой. Там он имел возможность попрактиковаться в программировании гигантских мейнфреймов IBM на машинном языке с помощью перфокарт, по карте на строку программы. Он оставлял свою стопку карт в компьютерном центре и на следующий день приходил за выдачей программы. Он мог просчитывать машину Тьюринга и в уме: пиши 0, пиши 1, пиши пробел, сдвиг ленты влево, сдвиг ленты вправо... Универсальный компьютер дал ему приятную возможность различать числа, такие как А и Б Алисы и Боба. Он мог написать программу для машины Тьюринга, чтобы та напечатала 010101... миллион раз, и он мог записать длину этой программы, довольно короткой. Но в случае миллиона случайных чисел — без закономерностей, без регулярности в появлении, вообще без каких-либо специальных свойств — упрощения быть не могло. Компьютерная программа должна была содержать в себе число целиком. Чтобы мейнфрейм IBM напечатал этот миллион знаков, ему пришлось бы включить весь миллион в перфокарты. Чтобы заставить это сделать машину Тьюринга, Хайтину все равно пришлось бы ввести миллион знаков.
Вот еще число (на сей раз в десятичной системе):
Оно выглядит случайным. Статистически каждый знак появляется с ожидаемой частотой (один из десяти), аналогично каждая пара знаков (один из сотни), каждая тройка и так далее. Статистик сказал бы, что число выглядит “нормальным”, насколько вообще кто-нибудь может что-то про него сказать. Следующий знак всегда непредсказуем. Когда-нибудь там появятся и пьесы Шекспира. Но кто-то может распознать эту цепочку чисел как хорошо знакомое число я. Получается, что это все-таки не случайное число.
Но почему мы говорим, что я не случайное число? Хайтин предложил четкий ответ: число не является случайным, если оно вычислимо — если определенная компьютерная программа его сгенерирует. Таким образом, вычислимость есть мера случайности.
Для Тьюринга вычислимость — это выбор, “да” или “нет”, данное число либо вычислимо, либо нет. Но нам хотелось бы иметь возможность сказать, что некоторые числа более случайны, чем другие, — они менее закономерны, в них меньше порядка. Хайтин сказал, что закономерности и порядок выражают вычислимость. Алгоритмы генерируют закономерности. Значит, мы можем измерить вычислимость, посмотрев на размер алгоритма. Имея число, представленное строкой любой длины, мы спрашиваем: какова длина наикратчайшей программы, с помощью которой оно может быть получено? Если мы используем язык машины Тьюринга, у этого вопроса может появиться конкретный ответ, выраженный в битах.
Алгоритмическое определение случайности Хайтина дает также алгоритмическое определение информации: размер алгоритма отражает и количество информации, которое содержится в данной строке.
Поиск структур, порядка среди хаоса — этим тоже заняты ученые. Восемнадцатилетний Хайтин чувствовал, что это неслучайно. Он закончил статью, применив алгоритмическую теорию информации к самому процессу научного познания. “Рассмотрим ученого, — предложил он, — наблюдавшего замкнутую систему, которая раз в секунду либо посылает луч света, либо нет”.
Он собирает свои наблюдения в последовательность из 0 и 1, где 0 соответствует состоянию “луча не было”, a 1 — состоянию “луч был”. Последовательность может начинаться так:0110101110... —и продолжаться еще несколько тысяч битов. Затем ученый изучает последовательность в надежде найти какую-нибудь закономерность или закон. Что он имеет под этим в виду? Кажется правдоподобным, что последовательность из 0 и 1 незакономерна, если только не существует лучшего способа вычислить ее, чем просто списать всю целиком из таблицы, где она представлена полностью.
Но если ученый смог найти способ сгенерировать такую же последовательность с помощью алгоритма, компьютерной программы, существенно более короткой, чем сама последовательность, то тогда он с уверенностью может сказать, что события не были случайными. Он скажет, что наткнулся на теорию. Это то, чего всегда добивается наука: простая теория, которая описала бы как можно больше фактов и позволила бы предсказывать будущие события. Это знаменитая бритва Оккама. “Мы должны признавать не больше причин естественных вещей, чем необходимо и достаточно для объяснения их появления, — говорил Ньютон. — Природа довольствуется простотой”. Ньютон количественно определил массу и силу, но простоте пришлось подождать.
Хайтин послал свою статью в Journal of the Association for Computing Machinery. Там были рады ее опубликовать, но один из рецензентов упомянул, что до него доходили слухи об аналогичной работе из Советского Союза. И действительно, в начале 1966 года прибыл первый выпуск нового журнала “Проблемы передачи информации”, и в нем была статья, озаглавленная “Три подхода к определению понятия “количество информации” академика А. Н. Колмогорова. У Хайтина, который не читал по-русски, хватило времени только на то, чтобы добавить сноску.
Андрей Николаевич Колмогоров был выдающимся математиком советской эпохи. Он родился в 1903 году в Тамбове, 300 милями юго-восточнее Москвы; его незамужняя мать, одна из трех сестер Колмогоровых, умерла при родах, и его вырастила тетка Вера в деревне на Волге. В последние годы царской России Вера занималась образованием деревенских детей и у себя дома на печатном прессе размножала запрещенные документы, порой пряча их под люлькой Андрея.
Андрей Николаевич поступил на математический факультет Московского университета вскоре после революции 1917 года. За десять лет в науке он добился значительных результатов, которые позже переросли в то, что мы знаем как теорию вероятности. Его “Основы теории вероятности”, опубликованные на русском в 1933-м и на английском в 1950-м, остаются современной классикой. Но его интересы простирались шире, до физики и лингвистики, интересовался он и другими быстро развивающимися отраслями математики. Однажды он вступил на территорию генетики, но быстро ретировался после опасной стычки с любимцем Сталина Трофимом Лысенко. Во время Второй мировой войны Колмогоров применил свои открытия в теории статистики в области артиллерии и разработал схему размещения аэростатов для защиты Москвы от нацистских бомбардировщиков. Он работал на оборону, изучал турбулентность и случайные процессы. Герой Социалистического Труда, он был семь раз награжден орденом Ленина.
Впервые Колмогоров увидел “Математическую теорию связи” Клода Шеннона в русском переводе в 1953 году; из книги переводчиком и цензурой были вычищены самые интересные идеи. Название превратилось в “Статистическую теорию передачи электрических сигналов”. Слово “информация” было везде заменено словом “данные”. Слово “энтропия” было взято в кавычки, чтобы у читателя, не дай бог, не возникло ассоциации с физикой. Раздел, в котором теория информации применялась к статистике естественного языка, был полностью опущен. В результате получилась техническая нейтральная, безжизненная книга, которую вряд ли кто-то захотел бы интерпретировать в терминах марксистской идеологии. На то имелись серьезные основания: в “Кратком философском словаре” “кибернетика” была определена как “реакционная лженаука” и “идеологическое оружие империалистической реакции”. Колмогоров тем не менее ухватился за статью Шеннона; ученый по крайней мере не боялся употреблять слово “информация”. Со студентами в Москве он разработал строгую математическую формулировку теории информации с определениями фундаментальных понятий, аккуратными доказательствами и новыми открытиями, причем некоторые из них, как он скоро с сожалением узнал, были опубликованы в первоначальной статье и опущены в русской версии.
В Советском Союзе, все еще изолированном от остального научного мира, Колмогоров был прекрасным кандидатом на роль знаменосца информации. Он отвечал за раздел математики в “Большой советской энциклопедии”, выбирал авторов, редактировал статьи и много писал сам. В 1956 году он подготовил большой отчет о теории передачи информации. Его коллеги думали, что он немного “запутался” — что работа Шеннона была “скорее техникой, чем математикой”, как позже вспоминал Колмогоров: “Правда, строгое математическое обоснование своих идей Шеннон в сколько-либо трудных случаях предоставил своим продолжателям. Однако его математическая интуиция изумительно точна”.
Колмогоров не испытывал энтузиазма по поводу кибернетики. Норберт Винер чувствовал, что у них с Колмогоровым есть нечто общее — они оба сначала работали над стохастическими процессами и броуновским движением. Во время визита в Москву Винер сказал: “Когда я читаю труды академика Колмогорова, я чувствую, что это и мои мысли, это то, что я хотел сказать. И я знаю, что такие же чувства испытывает академик Колмогоров, читая мои труды”. Но, по всей видимости, чувство все же не было взаимным. Колмогоров направлял своих коллег к теории Шеннона. “Легко понять, что математическая дисциплина кибернетика в понимании Винера лишена единства, — заявлял он, — и трудно себе представить продуктивную работу по подготовке, скажем, аспиранта по кибернетике в этом смысле”. У него уже были реальные результаты, чтобы подкрепить свою точку зрения: полезное обобщение формулировки энтропии Шеннона и расширение его меры информации на различные процессы.
В России наконец началось движение в сторону признания любых научных исследований, которые могли способствовать разработкам в области электронной связи и вычислений. Эта работа началась почти с нуля. Бытовой электротехники практически не существовало; советская телефония вызывала уныние, будучи объектом бесконечно грустного русского юмора. По состоянию на 1965 год не существовало такой вещи, как прямая междугородняя связь. Число звонков все еще оставалось ниже числа посылаемых телеграмм — США миновали этот этап в предыдущем столетии. В Москве было меньше телефонов на душу населения, чем в любом крупном городе мира. Тем не менее Колмогоров и его студенты получали достаточно результатов, чтобы оправдать создание нового ежеквартального журнала “Проблемы передачи информации”, посвященного теории информации, теории шифрования, теории сетей и даже информации в живых организмах. Первый выпуск открывался статьей Колмогорова “Три подхода к определению понятия “количество информации” — это был практически манифест, который начал медленный путь к известности в кругах западных математиков.
“Существует лишь тонкий слой между тривиальным и недоступным. В этом слое и делаются математические открытия”, — писал Колмогоров в дневнике. В новом, количественном взгляде на информацию он увидел способ решения проблемы, которая ускользала от теории вероятности, — проблемы случайности. Сколько информации содержится в данном “конечном объекте”? Объектом могло быть число (последовательность знаков), сообщение или набор данных.
Он описал три подхода: комбинаторный, вероятностный и алгоритмический. Первый и второй были улучшенными подходами Шеннона. Они были сосредоточены на вероятности появления одного объекта из множества подобных — скажем, одного сообщения, выбранного из множества возможных. Как это будет работать, интересовался Колмогоров, когда объект — не просто символ в алфавите или свет в окне церкви, а что-то сложное — генетический организм или предмет искусства? Как измерить количество информации в “Войне и мире” Толстого? “Можно ли включить разумным образом этот роман в совокупность “возможных романов”, да еще постулировать наличие в этой совокупности некоторого распределения вероятностей?” — вопрошал он. Можно ли измерить количество генетической информации, скажем, кукушки, рассматривая распределение вероятности на множестве всех возможных видов?
Его третий подход к измерению количества информации, алгоритмический, избегал трудностей, связанных с множеством возможных объектов. Он был сосредоточен на самом объекте. Колмогоров ввел новое слово для того, что он пытался измерить, — сложность. Согласно его определению этого термина, сложность числа, сообщения или набора данных есть величина, противоположная простоте и порядку, и она опять соответствует информации. Чем проще объект, тем меньше информации он несет.
Чем выше сложность, тем больше информации. Колмогоров, в точности как Грегори Хайтин, поставил эту идею на солидное математическое основание, рассчитав сложность в терминах алгоритмов. Сложность объекта есть размер наименьшей компьютерной программы, необходимой для его создания. Объект, который может быть воспроизведен коротким алгоритмом, имеет небольшую сложность. С другой стороны, объект, требующий алгоритма длиной во столько же битов, сколько содержится в нем самом, имеет максимальную сложность.
Простой объект можно сгенерировать, рассчитать или описать всего несколькими битами. Сложный объект требует алгоритма из множества битов. В такой формулировке это кажется очевидным, но до данного момента не математически. Колмогоров выразил это так:
Интуитивное различие между простыми и сложными объектами ощущалось, по-видимому, давно. На пути его формализации встает очевидная трудность: то, что просто описывается на одном языке, может не иметь простого описания на другом, и непонятно, какой способ описания выбрать.
Это затруднение было устранено путем использования языка вычислительной машины. Неважно, какого языка вычислительной машины, потому что они все эквивалентны, сводимы к языку универсальной машины Тьюринга. Колмогоровская сложность объекта есть размер в битах кратчайшего алгоритма, необходимого для генерации этого объекта. Это также и количество информации. И это также степень случайности — Колмогоров объявил о новой концепции понятия случайного, соответствующей естественному предположению, что случайность есть отсутствие регулярности. На самом деле информация, случайность и сложность эквивалентны, это три мощные абстракции, всегда связанные друг с другом, как тайные любовники.
Для Колмогорова данные идеи принадлежали не только теории вероятности, но и физике. Для измерения сложности упорядоченного кристалла или сосуда со случайным газом достаточно измерить наикратчайший алгоритм, необходимый для описания состояния кристалла или газа.
И снова ключом оказывается энтропия. У Колмогорова был полезный опыт в решении сложных физических проблем, к которым можно применить новый метод. В 1941 году ученый дал первое полезное, хотя и неточное описание локальной структуры турбулентности. Он также работал над пертурбациями планетарных орбит — еще одной проблемой, упрямо не поддающейся классической физике Ньютона. Теперь, анализируя динамические системы в терминах энтропии и информации, он начал закладывать фундамент для возрождения теории хаоса, которая возникнет в 1970-е. Имело смысл сказать, что динамическая система производит информацию. Если она непредсказуема, она производит очень много информации.
Колмогоров ничего не знал о Грегори Хайтине и никто из них двоих ничего не знал об их американском коллеге Рэе Соломоноффе, занимавшемся теорией вероятности, хотя тот разработал некоторые из тех же идей. Мир менялся. Время, расстояние и язык все еще отделяли математиков России от их коллег на западе, но с каждым годом разрыв становился все меньше. Колмогоров часто говорил, что никто не должен заниматься математикой после шестидесяти. Он мечтал провести старость на Волге в весельной лодке с маленьким парусом и работать бакенщиком. Но прошло время, бакенщики пересели на моторные лодки, и для Колмогорова это было концом мечты.
Вернулись парадоксы.
Ноль — интересное число, о нем написаны книги. Единица, безусловно, интересное число — она первая, в том числе и по порядку (не считая ноля), единственная и уникальная. Двойка интересна во всех отношениях: наименьшее простое число; число, определяющее четность; число, необходимое для успешного брака; атомное число гелия; число свечей, зажигаемых на финский День независимости. Интересно — обычное общеупотребительное слово, не математический жаргон. Кажется, о любом небольшом числе можно сказать, что оно интересное. Все двузначные и многие трехзначные числа имеют по статье в “Википедии”.
Ученые, занимающиеся теорией чисел, называют целые классы интересных чисел: простые, совершенные, квадраты и кубы, числа Фибоначчи, факториалы. Число 593 более интересно, чем выглядит на первый взгляд; это сумма квадрата девяти и двойки в девятой степени, следовательно, является числом Лейланда (любое число, которое можно выразить формулой ху + ух). Википедия посвятила статью числу 9814072356. Это наибольший квадрат, в котором содержатся все цифры по одному разу.
Тогда что же такое неинтересное число? Предположительно, случайное число. Английский исследователь теории чисел Г.Х. Харди в 1917 году ехал в такси 1729, чтобы посетить больного коллегу Сриниваса Рамануджана, и сообщил ему по приезде, что, судя по всему, 1729 — “довольно скучное число”. Напротив, ответил Рамануджан (согласно стандартному анекдоту математиков), это наименьшее число, которое можно получить суммой двух кубов двумя различными способами. “Каждое положительное целое число является другом Рамануджана”, — заметил Дж. Э. Литтлвуд. Благодаря анекдоту, 1729 сегодня известно как число Харди — Рамануджана. Но и это не все:, 1729 также является числом Кармайкла, псевдопростым числом Эйлера и числом Цейзеля.
Но даже ум Рамануджана конечен, так же как и “Википедия”, так же как и совокупное знание человечества, поэтому список интересных чисел должен когда-нибудь исчерпать себя. Наверняка должно существовать число, о котором нельзя сказать ничего особенного. Где бы оно ни было, сразу же возникнет парадокс: число, которое мы можем описать, интересно нам как “наименьшее неинтересное число”.
Это не что иное, как вновь появившийся парадокс Берри — тот самый, описанный Бертраном Расселом в “Принципах математики”. Берри и Рассел задали дьявольски хитрый вопрос: “Каково наименьшее целое число, которое нельзя назвать менее чем 19 слогами?” Каким бы это число ни было, его можно назвать 18 слогами: наименьшее натуральное число, которое невозможно назвать менее чем 19 слогами. Объяснения того, почему число интересно, — это на самом деле способы назвать это число: “квадрат семи”, например, или “число звезд на американском флаге”. Некоторые из этих названий не кажутся особенно полезными, а некоторые довольно нечеткие. Некоторые представляют собой чисто математические факты — например, можно ли выразить число суммой двух кубов двумя разными способами. Но некоторые представляют собой сведения о мире, языке или людях, и они могут быть случайны и эфемерны — например, соответствует ли число количеству остановок метро или исторической дате.
Хайтин и Колмогоров оживили парадокс Берри, придумав алгоритмическую теорию информации. Алгоритм называет число. “Парадокс первоначально говорит об английском языке, но это слишком размыто, — заявил Хайтин. — Вместо этого я выбрал язык программирования”. Естественно, он выбрал язык универсальной машины Тьюринга.
Вопрос: как вы называете целое число? Вы называете целое число, определяя способ его вычисления. Программа называет целое число, если ее выводом является это целое число — вы знаете, что она выдает это целое число, всего одно, а затем останавливается.
Вопрос, интересно ли число, обратен вопросу, случайно ли оно. Если число n можно вычислить с помощью алгоритма, который сравнительно короток, то n интересно. Если нет, то оно случайно. Алгоритм, печатающий 1 и затем 100 нулей, генерирует интересное число (оно называется гугол). Аналогично, найдите первое простое число, прибавьте следующее простое число и повторите это миллион раз — вы получите интересное число, сумму первого миллиона простых чисел. У машины Тьюринга вычисление этого числа заняло бы большое, но тем не менее конечное количество времени. Это число вычислимо.
Но если наикратчайший алгоритм для n есть “напечатать n” — алгоритм, включающий в себя все число, без сокращений, — то мы можем сказать, что ничего интересного в n нет. В терминах Колмогорова, это число случайно — оно максимально сложное. В нем в обязательном порядке должна содержаться любая структура, поскольку закономерность дала бы способ придумать сокращение алгоритма. “Если существует небольшая, краткая компьютерная программа, которая вычисляет число, — значит, оно имеет некое качество или особенность, которая позволяет вам выбрать его и сжать в более короткое алгоритмическое описание, — отмечал Хайтин. — Поэтому это необычно; это интересное число”.
Но необычно ли это? Откуда математик может знать, часто или редко встречаются интересные числа, рассматривая вообще все числа? Рассматривая одно конкретное число, способен ли математик когда-либо с уверенность сказать, что более короткий алгоритм может быть найден? Для Хайтина это были чрезвычайно важные вопросы.
На первый он ответил с помощью подсчета. Подавляющее большинство чисел должны быть неинтересны, потому что не может существовать достаточного количества лаконичных компьютерных программ, чтобы описать все. Посчитайте их. При длине в 1000 бит (к примеру) мы имеем 21000 чисел, но совсем не так много полезных вычислительных программ можно записать в 1,000 бит. “Существует множество других положительных целых чисел”. Так что большинство n любой заданной длины случайны.
Следующий вопрос был гораздо более проблематичным. Зная, что большинство чисел случайно, и имея любое конкретное n, может ли математик доказать, что оно случайно? Этого нельзя сказать, посмотрев на число. Наоборот, зачастую n оказывается интересным, в этом случае просто надо найти алгоритм, генерирующий его. (Технически он должен быть короче log2n бит — числа, соответствующего записи n в двоичной системе.) Доказательство обратного — другая история. “Даже несмотря на то, что большинство положительных целых чисел неинтересны, — заявил Хайтин, — никогда нельзя быть уверенным... Доказать это вы можете только в небольшом числе случаев”. Можно представить попытку доказательства прямым перебором, записав все возможные алгоритмы и проверяя их один за другим. Но вычислительной машине придется проводить проверки, выполнять алгоритм над другими алгоритмами, и скоро, как продемонстрировал Хайтин, появится новая версия парадокса Берри. Вместо “наименьшего неинтересного числа” мы неизбежно столкнемся с утверждением в форме “наименьшее число, для которого мы можем доказать, что его нельзя назвать менее чем n слогами”. (На самом деле мы, конечно, говорим уже не о слогах, а о состояниях машины Тьюринга.)
Опять замкнутый круг. Неполнота Геделя в версии Хайтина. Сложность, определенная в терминах размера программы, как правило, невычислима. Имея произвольную строку из миллиона знаков, математик знает, что она почти наверняка случайна, сложна и бессистемна, но не может быть в этом абсолютно уверен.
Хайтин завершил эту работу в Буэнос-Айресе. До того как он окончил Сити-колледж, его родители вернулись в Аргентину, и он поступил на работу в торговое подразделение IBM. Он продолжал лелеять страсть к Геделю и неполноте и посылал статьи в Американское математическое общество и Ассоциацию вычислительных машин. Восемь лет спустя Хайтин вернулся в США, чтобы посетить исследовательский центр IBM в Йорктаун-Хайтс, Нью-Йорк, и позвонил своему тогда уже почти 70-летнему герою в Институт перспективных исследований в Принстоне. Гедель ответил, Хайтин представился и сказал, что у него есть новый подход к неполноте, основанный на парадоксе Берри, а не на парадоксе лжеца.
— Не имеет значения, какой парадокс вы используете, — ответил Гедель.
— Да, но... — Хайтин сказал, что находится в поиске нового “информационно-теоретического” взгляда на неполноту, и спросил, может ли он посетить Геделя в Принстоне. Он остановился бы в Юношеской христианской ассоциации в Уайт-Плейнс и поехал бы поездом, сделав пересадку в Нью-Йорке. Гедель согласился, но, когда наступил назначенный день, отменил встречу. Шел снег, и он боялся за свое здоровье. Хайтин так никогда с ним и не встретился. Гедель становился все менее адекватным, ему казалось, что его хотят отравить, и зимой 1978 года он умер от истощения.
Хайтин работал в Исследовательском центре IBM им. Томаса Джона Уотсона и был одним из последних великих ученых, чьи исследования поддерживали, несмотря на отсутствие убедительной пользы для корпорации. Он иногда говорил, что “прятался” в отделе физики; Хайтин чувствовал, что математики более традиционного толка все равно считали его “скрытым физиком”.
Его работа рассматривала математику как своего рода эмпирическую науку; не путь Платона к абсолютной истине, а программа исследований, подверженная всем условностям и неопределенности мира. “Несмотря на неполноту, невычислимость, даже алгоритмическую случайность, — говорил он, — математики не желают отказываться от абсолютной уверенности. Почему? Ну, абсолютная уверенность — как Господь”.
В квантовой физике, а позже и в теории хаоса ученые обнаружили пределы своих знаний. Они изучали неопределенность, сначала так расстроившую Эйнштейна, который не хотел верить в то, что Господь играет в кости со Вселенной. Алгоритмическая теория информации применяет те же ограничения к вселенной целых чисел, идеальной и умозрительной. Как сказал Хайтин, “Бог играет в кости не только в квантовой физике и нелинейной динамике, но даже в элементарной теории чисел”.
Среди его уроков были следующие.
• Большинство чисел случайно. Тем не менее доказать случайность можно для очень немногих из них.• Хаотичный поток информации может скрывать простой алгоритм. Пройти путь назад от хаоса к алгоритму, скорее всего, невозможно.• Сложность Колмогорова — Хайтина (КХ) в математике означает то же, что энтропия в термодинамике, — антидот совершенству. Точно так же, как не может быть вечного двигателя, не может существовать полной формальной аксиоматической системы.• Некоторые математические факты истинны без причины. Они случайны, у них нет обоснования или более глубокого, скрытого значения.
Джозеф Форд — физик, в 1980-е изучающий поведение непредсказуемых динамических систем, — говорил, что Хайтин “чудесно ухватил суть вещей”, показав путь от неполноты Геделя к хаосу. Это был “глубинный смысл хаоса”, заявил Форд.
Хаотичные орбиты существуют, но они, дети Геделя, настолько сложны, настолько перегружены информацией, что люди никогда не смогут осмыслить их. Хаос есть повсюду в природе; таким образом, вселенная наполнена бесчисленными загадками, которые человек никогда не сможет разгадать.
Тем не менее мы все еще пытаемся их измерить.
Сколько информации?..
Когда объект (число, поток битов или динамическую систему) можно представить другим способом, с помощью меньшего количества битов, он сжимаем. Экономный оператор телеграфа предпочитает посылать сжатую версию. Поскольку дух бережливого телеграфиста поддерживался в Лабораториях Белла, для Клода Шеннона естественным было заняться исследованием сжатия данных и в теории, и на практике. Сжатие было важной проблемой: военная работа Шеннона по криптографии анализировала сокрытие информации на одном конце и восстановление на другом; аналогично, сжатие данных кодирует информацию, но с целью эффективного использования полосы частот. Спутниковые телевизионные каналы, карманные музыкальные проигрыватели, эффективные камеры и телефоны и бесчисленное множество других современных приспособлений зависят от алгоритмов кодирования для сжатия чисел, последовательностей битов, и эти алгоритмы ведут свое происхождение от статьи Шеннона 1948 года.
Первый такой алгоритм, теперь известный как кодирование Шеннона — Фано, предложил его коллега Роберт М. Фано. Все началось с простой идеи заменить часто встречающиеся символы более короткими кодами, как в азбуке Морзе. Однако ученые знали, что это не оптимальный метод, от него нельзя ожидать генерации кратчайшего из возможных сообщений, и через три года его превзошла работа Дэвида Хаффмана, аспиранта Фано в МТИ. За прошедшие с тех пор десятилетия различные версии алгоритма Хаффмана сжали очень много битов.
Рэй Соломонофф, сын русских эмигрантов, который учился в Университете Чикаго, познакомился с работой Шеннона в начале 1950-х и задумался над тем, что он назвал задачей упаковки информации: сколько информации можно “упаковать” в данное количество битов или, наоборот, имея некоторую информацию, как ее упаковать в наименьшее количество битов. Основным его предметом была физика, а математическую биологию, теорию вероятности и логику он изучал дополнительно. Он познакомился с Марвином Мински и Джоном Мак-Карти, пионерами в той области, которая скоро станет известна как искусственный интеллект. Потом он прочитал необычную и оригинальную статью Ноама Хомского “Три модели описания языка”, в которой тот применил новые идеи теории информации к формализации языковой структуры. Соломонофф не до конца представлял, куда все это ведет, но обнаружил, что сосредоточился на проблеме индукции. Как люди создают теории, объясняющие их опыт в этом мире? Им приходится делать обобщения, искать закономерности в данных, которые всегда находятся под влиянием случайности и шума. Можно ли научить этому машину? Другими словами, может ли компьютер учиться на опыте?
Он получил сложный ответ, который опубликовал в 1964 году. Его работа была единственной в своем роде, и ее вряд ли кто-то заметил, пока в 1970-х Хайтин и Колмогоров не обнаружили, что Соломонофф описал черты того, что потом станет алгоритмической теорией информации. Фактически Соломонофф тоже пытался понять, как компьютер может воспринимать последовательность данных — последовательности чисел или строки битов — и измерять их случайность и скрытые структуры. Когда люди или компьютеры учатся на своем опыте, они используют индукцию — распознают регулярности в нерегулярных потоках информации. С этой точки зрения законы науки представляют собой сжатие данных в действии. Физик-теоретик действует как очень умный кодирующий алгоритм. “Уже открытые научные законы можно рассматривать как результат обработки большого количества эмпирических данных о вселенной, — писал Соломонофф. — В текущем контексте каждый такой закон можно преобразовать в метод компактного кодирования эмпирических данных, из которых и был получен этот закон”. Хорошая научная теория экономна, и вот еще один способ сказать об этом.
Соломонофф, Колмогоров и Хайтин, решая три разные задачи, пришли к одному и тому же решению. Соломонофф интересовался индуктивными выводами: как наилучшим образом предсказать следующее событие, имея последовательность наблюдений? Колмогоров искал математическое определение случайности: что значит утверждение, что одна последовательность более случайна, чем другая, когда они имеют одинаковые вероятности в серии подбрасываний монеты? Хайтин пытался найти путь к неполноте Геделя через Тьюринга и Шеннона, как он позже говорил, “поместив теорию информации Шеннона и теорию вычислимости Тьюринга в шейкер и ожесточенно взбалтывая”. Все пришли к минимальной длине программы. И к разговору о сложности.
Следующая последовательность битов (или число) не слишком сложна, потому что рациональна:
Ее можно кратко записать как “напечатать 142857 и повторить” или еще короче: “1/7”. Если это сообщение, сжатие уменьшит количество ударов по клавишам. Если это входящий поток данных, наблюдатель сможет распознать закономерность, убедиться в ее наличии и удовлетвориться одной седьмой как теоретическим описанием.
Напротив, следующая последовательность заканчивается неожиданно:
Телеграфист (или теоретик, или алгоритм сжатия) должен принимать во внимание все сообщение целиком. Тем не менее, дополнительная информация минимальна; сообщение все еще можно сжать, если есть какая-то закономерность. Можно сказать, что оно состоит из избыточной и произвольной частей.
Шеннон первым показал, что все неслучайное в сообщении позволяет его сжимать.
Много единиц, мало нулей, последовательность могла быть сгенерирована подбрасыванием неправильной монеты. Кодирование Хаффмана и другие подобные алгоритмы используют статистические закономерности для сжатия данных. Фотографии сжимаемы благодаря естественной избыточности изображенного на них: светлые и темные пиксели появляются кластерами; статистически находящиеся рядом пиксели с большей вероятностью будут одинаковыми; пиксели, не находящиеся в непосредственной близости, не будут. Видео еще более доступно для сжатия, потому что разница между одним кадром и следующим сравнительно невелика, за исключением случая, когда объект находится в быстром и беспорядочном движении. Естественный язык можно сжать, потому что существуют избыточность и закономерности, о которых говорил Шеннон. Только полностью случайная последовательность остается несжимаемой, появление каждого из ее событий — неожиданность.
Случайные последовательности “нормальны” — специальный термин, означающий, что в среднем на большой выборке каждая цифра появляется так же часто, как и другие, один раз из десяти; каждая пара цифр, от 00 до 99, появляется один раз из сотни; каждая тройка — аналогично и т.д. Никакая строка определенной длины не появляется с большей вероятностью, чем любая другая последовательность этой длины. Нормальность — одна из тех идей, которые кажутся простыми, но при ближайшем рассмотрении математиками оказываются полны опасностей. Несмотря на то, что настоящая случайная последовательность обязана быть нормальной, обратное утверждение не обязательно верно. Число может быть статистически нормальным, но совершенно не случайным. Дэвид Чамперноун, молодой друг Тюринга из Кембриджа, в 1933 году придумал (или открыл, если угодно) конструкцию, состоящую из всех целых чисел, выстроенных по порядку:
Нетрудно видеть, что каждый знак и каждая комбинация знаков на большой выборке появляются с одинаковой частотой. Тем не менее эту последовательность нельзя назвать случайной. Она строго структурирована и полностью предсказуема. Если вы знаете, где находитесь, вы знаете, что будет дальше.
Даже без таких чудачеств нормальные числа оказалось трудно распознать. Во вселенной чисел нормальность — это правило; математики точно знают, что почти все числа нормальны. Рациональные числа ненормальны, и существует бесконечное количество рациональных чисел, но это количество бесконечно меньше количества нормальных чисел. Тем не менее, ответив на великий глобальный вопрос, математики почти никогда не могут доказать, что какое-то конкретное число нормально. Это одна из самых примечательных странностей математики.
Даже число π хранит свои тайны:
Компьютеры мира прошли множество циклов, анализируя первый триллион или около того знаков этого космического послания, и, насколько можно сказать, эти знаки кажутся нормальными. Не было обнаружено никаких статистических закономерностей — ни отклонений, ни корреляций, локальных или отдаленных. Это наиболее типичный пример неслучайного числа, которое на первый взгляд ведет себя как случайное. Нет никакого упрощенного способа, зная n-й знак, угадать n+1-й.
Сколько информации представляет эта последовательность знаков? Она богата информацией настолько, насколько случайно число? Или бедна как упорядоченная последовательность?
Телеграфист, конечно, мог бы сэкономить множество ударов по клавишам, бесконечно много, просто послав сообщение π. Но это жульничество. Оно подразумевает предварительное знание, общее для отправителя и получателя. Прежде всего, отправитель сам должен узнать эту специальную последовательность, а получатель должен знать, что такое π и как найти или вычислить его десятичное расширение. Фактически у них должна быть общая кодовая книга.
Однако это не означает, что π содержит много информации. Суть сообщения может быть послана меньшим количеством ударов клавиш. Телеграфист может использовать несколько стратегий. Например, сказать: “Возьми 4, вычти 4/3, прибавь 4/5, вычти 4/7 и так далее”. То есть выслать алгоритм.
Эта бесконечная серия дробей медленно сходится к π, так что получателю придется выполнить много работы, но само сообщение экономно: информация, содержащаяся в нем, остается той же независимо от того, сколько требуется десятичных знаков.
Проблема наличия общего знания на находящихся далеко друг от друга концах линии ведет к трудностям. Иногда людям нравится описывать такого рода проблемы, проблемы информационного содержания в сообщениях, в терминах связи с инопланетной формой жизни в далекой галактике. Что мы могли бы им сказать? Что бы мы хотели сказать? Законы математики универсальны, мы склонны думать, что я будет тем самым сообщением, которое поймет любая разумная раса. Но вряд ли можно ожидать, что они знают греческую букву. И вряд ли они узнают десятичные знаки 3,1415926535..., если только у них случайно не будет десяти пальцев.
Кодовая книга, находящаяся в голове того, кто получает сообщение, никогда не совпадет с кодовой книгой отправителя. Два огня в окне могут ничего не значить, а могут значить “Британцы идут морем”. В любой поэме есть сообщение, для каждого читателя разное. Есть возможность избавить такой способ мышления от неопределенности. Хайтин писал:
Предпочтительно рассматривать связь не с другом, а с цифровым компьютером. У друга могут оказаться способности делать выводы о числах или конструировать серии из частичной информации или нечетких инструкций. У компьютера нет таких способностей, для наших целей этот недостаток является преимуществом. Инструкции компьютеру должны быть полными и четкими, они должны дать ему возможность продвигаться вперед шаг за шагом.
Другими словами, сообщение — это алгоритм. Получатель — машина, у которой нет воображения, нет неуверенности, нет знания, кроме присущего структуре машины. К 1960-м цифровые компьютеры уже получали свои инструкции в форме, измеряемой в битах, поэтому естественно было рассуждать о том, сколько информации содержится в любом алгоритме.
Другим типом сообщения может быть такое:
Даже на глаз эта последовательность нот кажется неслучайной. Сообщение, представленное ими, уже движется сквозь межзвездное пространство в 10 млрд миль от своего источника, движется со скоростью в малую долю скорости света. Сообщение зашифровано не в этой форме, основанной на печати, и не в цифровой форме, а как микроскопические волны в единственной длинной бороздке, свернутой в спираль на диске в 12 дюймов диаметром и в 1/5 дюйма толщиной. Диск мог быть виниловым, но он сделан из меди и покрыт золотом. Этот аналоговый способ записи, хранения и воспроизведения звука был изобретен в 1877 году Томасом Эдисоном, которой назвал его фонографией. Данный способ оставался самой популярной аудиотехнологией и 100 лет спустя, и в 1977 году комитет, возглавляемый астрономом Карлом Саганом, организовал фонографическую запись и поместил ее копии в два космических корабля, Voyager 1 и Voyager 2, каждый размером с маленький автомобиль, которые были запущены летом с мыса Канаверал в штате Флорида.
Получилось сообщение в межзвездной бутылке. У него нет смысла, только структура: то же самое, что сказать, что это абстрактное искусство, — первая прелюдия Иоганна Себастьяна Баха из “Хорошо темперированного клавира” в фортепианном исполнении Гленна Гулда. Более общее сообщение, пожалуй, может быть таким: “Здесь есть разумная жизнь”. Кроме прелюдии Баха на пластинке оказались фрагменты народной музыки нескольких культур и подборка земных звуков: ветра, прибоя и грома, приветствия на пятидесяти пяти языках, голоса кузнечиков, лягушек и китов, корабельная сирена, стук повозки, которую тащит за собой лошадь, и сигналы азбуки Морзе. Вместе с фонографической записью там находится головка звукоснимателя и игла с краткой пиктографической инструкцией.
Комитет не стал беспокоиться о проигрывателе или источнике электричества. Может быть, в том, что служит им атмосферой, инопланетяне найдут способ преобразовать эти аналоговые металлические бороздки в волны или в другую подходящую их инопланетным чувствам форму.
Распознают ли они, что, например, сложная структура прелюдии Баха отличается от менее интересного, более случайного стрекотания кузнечиков? Записанные ноты, в конце концов, содержат суть произведения Баха. Еще более общий вопрос — какого рода знания, какого рода кодовая книга потребуются на том конце линии для расшифровки этого сообщения? Способность к восприятию контрапункта и многоголосия? Знакомство с тональностями и традициями исполнения музыки барокко? Звуки, ноты поступают группами; они принимают форму, которая называется мелодией, они подчиняются правилам имплицитной грамматики. Несет ли музыка свою логику, независимую от географии и истории? Тем временем на Земле в течение нескольких лет, еще до того, как Voyager 1 и 2 покинули пределы Солнечной системы, музыка уже редко записывалась в аналоговой форме. Лучше записать звуки “Хорошо темперированного клавира” как биты (волны, согласно теореме Шеннона о выборках, дискретизированные без потери) и сохранить информацию на дюжине подходящих носителей.
В терминах битов может показаться, что прелюдия содержит совсем немного информации. Написанная Бахом на двух рукописных страницах, она состоит из боо нот — знаков маленького алфавита. В том виде, в котором в 1964 году ее сыграл Гленн Гулд, добавив исполнительские нюансы и вариации, она длится 1 мин 36 с. Звук этого исполнения, перенесенный на CD в микроскопические углубления, выжженные лазером на тонком диске из поликарбоната, состоит из 135 млн бит. Но этот поток бит может быть значительно сжат без потери информации. С другой стороны, прелюдия помещается на маленьком ролике механического пианино (потомок станка Жаккарда и предшественник перфокарточных вычислительных машин); закодированная в формате MIDI она занимает несколько тысяч бит. Даже исходное сообщение в 600 знаков обладает огромной избыточностью: не меняющийся темп, один и тот же тембр, короткая мелодическая структура, слово, повторяющееся снова и снова с небольшими вариациями до последних тактов. Оно знаменито, обманчиво просто. Само повторение порождает ожидания и обманывает их. Практически ничего не происходит и одновременно все является неожиданностью. “Бессмертные ломаные аккорды ослепительных гармоник”, — говорила Ванда Ландовска. Прелюдия проста той простотой, что и полотна Рембрандта. Она делает многое, используя малое. Много ли в ней информации? Определенную музыку можно считать информационно бедной. На одном конце шкалы — композиция Джона Кейджа «4’33”», в которой нет ни одной ноты, просто 4 мин 33 с практически полной тишины. Практически, потому что это музыкальное произведение поглотило все окружавшие неподвижного пианиста звуки — движения слушателей в креслах, шорохи одежды, дыхание, вздохи.
Сколько информации в прелюдии Баха до мажор? Ее можно проанализировать, отследить и понять как структуру, существующую во времени и пространстве, но лишь до определенного предела. В музыке, как и в поэзии, как и в любом искусстве, полное понимание должно ускользать, так задумано. Если кому-то удалось бы достигнуть самой сути, все произведения искусства сразу стали бы скучны.
Поэтому использование программы минимальной длины как меры сложности кажется совершенным, подходящий апогей теории информации Шеннона. При этом он остается глубоко разочаровывающим. И это становится особенно очевидным, когда рассматриваются основополагающие — можно сказать, общечеловеческие — вопросы об искусстве, биологии и разуме.
В соответствии с этой мерой миллион нулей и миллион бросков монеты оказываются в противоположных концах спектра. Пустая строка настолько проста, насколько возможно, — случайная строка максимально сложна. Нули не несут информации — бросок монеты дает наибольшее возможное количество информации. Тем не менее у этих крайностей есть нечто общее. Они скучны. Они не обладают ценностью. Если бы любая из них была сообщением из другой галактики, мы не посчитали бы ее отправителя разумным существом. Если бы они были музыкой, они были бы точно так же бесполезны.
Все, что нам важно, лежит где-то посередине — там, где соединяются порядок и случайность.
Хайтин и его коллега Чарльз Беннет иногда обсуждали эти вопросы в исследовательском центре IBM в Иорктаун-Хайтс, Нью-Йорк. Беннет потратил годы и разработал новую меру ценности, которую назвал “логической глубиной”. Идея глубины Беннета связана со сложностью, но ортогональна ей. Она предназначена для измерения полезности сообщения, что бы ни означала полезность в каждой конкретной области. “С самого начала теория информации признавала, что сама по себе информация не лучшим образом отражает ценность сообщения”, — написал он, когда наконец в 1988 году опубликовал свою схему.
Типичная последовательность бросков монеты имеет высокое информационное наполнение, но низкую ценность; эфемериды, в которых записаны положение Луны и планет на каждый день в течение 100 лет, обладают не большим количеством информации, чем уравнения движения и начальные условия, с помощью которых эти эфемериды были рассчитаны, но избавляют их владельца от усилий снова и снова рассчитывать эти положения.
Количеством работы, которую необходимо произвести для расчетов, во всех теоретических выкладках на основе машин Тьюринга чаще всего пренебрегали. Беннет вернул эту работу. Нет логической глубины в тех частях сообщения, которые являются чистой случайностью и непредсказуемы, и нет логической глубины в очевидной избыточности, в простом повторении и копировании. Ценность сообщения, предположил ученый, скорее лежит в том, “что можно назвать его скрытой избыточностью — в частях, предсказуемых лишь с трудом, в вещах, о которых получатель мог бы догадаться и без сообщения о них, но лишь за счет существенных денежных, временных или вычислительных затрат”. Когда мы оцениваем сложность объекта или его информационное содержание, мы чувствуем присутствие длительных скрытых вычислений. Это может быть верно в отношении музыки, стихов, научной теории или не слишком сложного и не слишком легкого кроссворда, который доставляет удовольствие решившему его человеку.
Математики и логики выработали тенденцию думать об информационном процессе как о бесплатном — не таком, как перекачка воды или перенос камней. В наше время он действительно стал недорогим. Но, в конце концов, в него входит работа, и Беннет предложил признать эту работу, учесть затраты на нее при рассмотрении сложности. “Чем менее различим объект, тем труднее его обнаружить”, — заявил Беннет. Он применил идею логической глубины к проблеме самоорганизации — к вопросу о том, как развиваются сложные структуры в природе. Эволюция начинается с простых начальных условий: сложность возрастает как результат предыдущего усложнения. Какими бы ни были основные процессы, физическими или биологическими, происходит что-то еще, похожее на вычисления.
Назад: Глава 11. В МЕМОФОНД. Вы паразитируете на моем мозге
Дальше: Глава 13. ИНФОРМАЦИЯ КАК ФИЗИЧЕСКАЯ ВЕЛИЧИНА. Все из бита
