11,0010010000111111011010101000100010000101101000110000100011010011…
И снова мы сталкиваемся с бесконечным рядом непредсказуемых нулей и единиц. В соответствии с определением энтропии Шеннона, число π содержит бесконечное количество информации, поскольку каждый его знак соответствует одному биту, и таких знаков бесконечное количество.
Многие математики предполагают, что, поскольку число знаков К бесконечно и они следуют в случайном порядке, должна существовать такая последовательность внутри числа π, которая соответствовала бы полному содержанию «Одиссеи» в двоичном коде. Или должна быть последовательность, соответствующая двоичному представлению всех фотографий, которые читатель когда-либо сделал в своей жизни. Но подобные предположения пока остаются недоказанными.
Теория информации Шеннона имеет принципиальное значение для разработки эффективных систем коммуникации, в которых нужно не только передать сообщение с минимальными затратами энергии, но и учитывать ошибки при передаче и предусмотреть возможность их исправления. В нашу эпоху телекоммуникаций энтропия Шеннона стала чрезвычайно важным компонентом технологий.
Другая область применения теории информации — лингвистика, где энтропия Шеннона используется для анализа избыточности языковых средств. Один из самых удивительных результатов формулируется следующим образом: из каждого текста можно исключить половину букв, и информация при этом сохранится. Как видите, язык — крайне избыточный инструмент для передачи сообщений. Также было открыто, что обычно самые короткие слова в языке встречаются чаще всего — в соответствии с законом минимального усилия, в котором можно увидеть параллель с принципом наименьшего действия в физике.
Поскольку любой физический или биологический процесс влечет за собой обмен и обработку информации, теория информации может применяться в изучении живых систем, например для определения плотности информации, содержащейся в молекуле ДНК. С этой точки зрения может быть проанализирован и человеческий мозг, поскольку этот орган в основном занимается обработкой информации. Последние оценки говорят о нашей способности обрабатывать примерно 50 битов в секунду. Подтверждает это и скорость нашего чтения: обычный человек читает около страницы в минуту. Если предположить, что на странице примерно триста слов, это составит около пяти слов в секунду, а если принять, что в слове 10 битов, окажется, что человек обрабатывает 50 битов в секунду.
Однако наши органы могут получить гораздо большее количество информации о внешнем мире. Так, глаза посылают в наш мозг около 10 млн битов в секунду. Но сырая информация, которую мы получаем, перед передачей в наши центры аналитической обработки должна быть очень сильно сжата.
Мы видели, что, согласно теории Шеннона, количество информации, содержащееся в числе π у бесконечно. Но существует и другой способ восприятия данных: например, мы можем предположить, что вся информация, необходимая для вычисления знаков π, содержится в математической формуле, описывающей это число, и, следовательно, нам не нужно бесконечное количество информации.
Этот альтернативный взгляд привел к появлению алгоритмической теории информации. Эта математическая теория, которая дополняет теорию Шеннона, была разработана сначала русским математиком Андреем Колмогоровым (1903–1987), а затем — аргентинско-американским математиком Грегори Хайтином (1947). Она основывается на понятии алгоритма — набора простых инструкций для компьютера. Ниже приведен пример алгоритма на вымышленном языке программирования, с помощью которого можно определить, является число символов во фразе четным или нечетным.
1. Посчитай число символов во фразе и сохрани результат в х.
2. Вычисли остаток деления х на два и сохрани результат в r.
3. Если r равен нулю, напиши на экране: «Число символов четное».
4. Если r не равен нулю, напиши на экране: «Число символов нечетное».
* * *
ГРЕГОРИ ХАЙТИН
Грегори Хайтин, родившийся в 1947 году, — аргентинско-американский программист и математик. Еще будучи подростком, он вывел алгоритмическую теорию информации и свою собственную версию теоремы Гёделя о неполноте, где показал, что количество недоказуемых теорем в математике намного больше, чем было принято считать. Сейчас Хайтин занимается метабиологией — математическим подходом к биологии, который изучает случайное развитие компьютерных программ для понимания биологической эволюции и возникновение творчества в строгой математической форме.
* * *
Согласно алгоритмической теории информации, информация, содержащаяся в цепочке символов, задана длиной самой короткой программы, которая ее порождает. Возьмем цепочку:
Существует программа, порождающая ее с помощью очень короткого кода.
1. Напиши единицу.
2. Вернись к началу программы.
В этой цепочке содержится очень мало информации.
Важно, что количество информации зависит от используемого языка программирования. Так, программа на языке Java и программа на языке С имеют разное количество строк, даже если обе делают одно и то же. Чтобы преодолеть эту проблему, воспользуемся понятием универсального языка программирования: язык программирования универсален, если его можно использовать для написания любой программы, которую можно написать на любом другом языке. Все существующие сегодня языки программирования универсальны, в том смысле что можно создать программу на языке Java, которая понимала бы программы, написанные на С, и наоборот. Хотя содержание информации в этих программах будет разным, эти отличия относительно небольшие и зависеть они будут не от количества строк кода, а от разницы между двумя языками программирования. А эта разница всегда постоянна.
Применим алгоритмическое определение информации к вычислению знаков числа π. Вспомним, что, согласно Шеннону, количество информации, содержащейся в числе π, бесконечно. Однако существует простая формула, которая позволяет довольно точно вычислить знаки этого числа. Выглядит она следующим образом:
На основании этой формулы можно создать очень короткую программу. И это означает, что в соответствии с алгоритмической теорией π не содержит бесконечного количества информации.
Как видите, в этом конкретном случае алгоритмический подход несколько отличается от предложенного Шенноном, но в большинстве других случаев они согласуются. Например, для передачи случайной последовательности нулей и единиц самой короткой программе необходимо столько же бит, сколько цифр содержится в цепочке.
Возникает вопрос: существует ли число, содержащее бесконечное количество информации по определению Колмогорова и Хайтина (подобное π в определении Шеннона)? Да, такое число существует, и это одно из самых удивительных чисел в истории математики — число омега, известное также как постоянная Хайтина. Ее свойство заключается в том, что эта постоянная не может порождаться кодом, содержащим меньше битов, чем она сама. Это означает, что все биты числа омега полностью случайны.
Для того чтобы понять, что такое постоянная Хайтина, поговорим о проблеме остановки, которая заключается в том, чтобы определить, остановится ли какая-либо программа. Так, мы знаем, что программа, вычисляющая 2 + 2, остановится, как только будет найдена требуемая сумма. Но точно так же программа, вычисляющая все простые числа, не остановится никогда. Можно доказать, что способа решить проблему остановки для любой программы не существует: мы можем узнать, остановится ли какая-то конкретная программа, но не можем сделать этого для любого алгоритма.
Например, представим себе программу, которой даны инструкции остановиться при нахождении четного числа, которое не может быть выражено как сумма двух простых. Программа остановится, если существует четное число с такими характеристиками, и никогда не остановится в противном случае. Ни один математик до сих пор не смог найти ответ на эту проблему, связанную с доказательством гипотезы Гольдбаха, в которой утверждается, что любое четное число может быть выражено как сумма двух простых чисел. Сегодня кажется, что гипотеза верна — по крайней мере, уже полученные результаты вычислений вполне ей соответствуют, но не доказано, что эта тенденция сохранится до бесконечности.
Постоянную Хайтина можно понимать как вероятность того, что программа, выбранная наугад, остановится. Предположим, что во Вселенной существуют только программы, содержащие три бита информации, то есть всего таких программ восемь: 000, 001, 010, 011, 100, 101, 110, 111. Если бы останавливалась только программа 000, вероятность остановки составила бы 1/8.
Итак, мы можем вычислить вероятность того, что программа, выбранная наугад, остановится, если сложим вероятности выбора всех останавливающихся программ.
Результат будет равен единице, деленной на число программ, содержащих 2n битов.
Используем для обозначения суммы символ Σ. Постоянная Хайтина в математической нотации записывается следующим образом:
Таким образом, число омега равно вероятности выбора случайной программы, которая остановится, и эта вероятность вычисляется суммированием вероятности выбора всех программ, которые останавливаются.
Число Хайтина имеет любопытные математические свойства. С одной стороны, его невозможно вычислить, поскольку для этого потребовалась бы программа с бесконечным числом битов. Также это число случайно, ведь если бы это было не так, можно было бы сжать содержащуюся в нем информацию и вычислить эту постоянную. Но самое важное — это то, что вычисление постоянной Хайтина позволяет решить проблему остановки для любой программы. Поскольку подавляющее большинство нерешенных математических задач можно свести к вопросу о том, ост