Эдуардо Арройо - Том 42. Путешествие от частицы до Вселенной. Математика газовой динамики

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

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

Поскольку любой физический или биологический процесс влечет за собой обмен и обработку информации, теория информации может применяться в изучении живых систем, например для определения плотности информации, содержащейся в молекуле ДНК. С этой точки зрения может быть проанализирован и человеческий мозг, поскольку этот орган в основном занимается обработкой информации. Последние оценки говорят о нашей способности обрабатывать примерно 50 битов в секунду. Подтверждает это и скорость нашего чтения: обычный человек читает около страницы в минуту. Если предположить, что на странице примерно триста слов, это составит около пяти слов в секунду, а если принять, что в слове 10 битов, окажется, что человек обрабатывает 50 битов в секунду.

Однако наши органы могут получить гораздо большее количество информации о внешнем мире. Так, глаза посылают в наш мозг около 10 млн битов в секунду. Но сырая информация, которую мы получаем, перед передачей в наши центры аналитической обработки должна быть очень сильно сжата.

Мы видели, что, согласно теории Шеннона, количество информации, содержащееся в числе π у бесконечно. Но существует и другой способ восприятия данных: например, мы можем предположить, что вся информация, необходимая для вычисления знаков π , содержится в математической формуле, описывающей это число, и, следовательно, нам не нужно бесконечное количество информации.

Этот альтернативный взгляд привел к появлению алгоритмической теории информации. Эта математическая теория, которая дополняет теорию Шеннона, была разработана сначала русским математиком Андреем Колмогоровым(1903–1987) , а затем — аргентинско-американским математиком Грегори Хайтином(1947) . Она основывается на понятии алгоритма — набора простых инструкций для компьютера. Ниже приведен пример алгоритма на вымышленном языке программирования, с помощью которого можно определить, является число символов во фразе четным или нечетным.

1. Посчитай число символов во фразе и сохрани результат в х .

2. Вычисли остаток деления х на два и сохрани результат в r .

3. Если r равен нулю, напиши на экране: «Число символов четное».

4. Если r не равен нулю, напиши на экране: «Число символов нечетное».

* * *

ГРЕГОРИ ХАЙТИН

Грегори Хайтин, родившийся в 1947 году, — аргентинско-американский программист и математик. Еще будучи подростком, он вывел алгоритмическую теорию информации и свою собственную версию теоремы Гёделя о неполноте, где показал, что количество недоказуемых теорем в математике намного больше, чем было принято считать. Сейчас Хайтин занимается метабиологией — математическим подходом к биологии, который изучает случайное развитие компьютерных программ для понимания биологической эволюции и возникновение творчества в строгой математической форме.

* * *

Согласно алгоритмической теории информации, информация, содержащаяся в цепочке символов, задана длиной самой короткой программы, которая ее порождает. Возьмем цепочку:

Существует программа, порождающая ее с помощью очень короткого кода.

1. Напиши единицу.

2. Вернись к началу программы.

В этой цепочке содержится очень мало информации.

Важно, что количество информации зависит от используемого языка программирования. Так, программа на языке Java и программа на языке С имеют разное количество строк, даже если обе делают одно и то же. Чтобы преодолеть эту проблему, воспользуемся понятием универсального языка программирования: язык программирования универсален, если его можно использовать для написания любой программы, которую можно написать на любом другом языке. Все существующие сегодня языки программирования универсальны, в том смысле что можно создать программу на языке Java , которая понимала бы программы, написанные на С , и наоборот. Хотя содержание информации в этих программах будет разным, эти отличия относительно небольшие и зависеть они будут не от количества строк кода, а от разницы между двумя языками программирования. А эта разница всегда постоянна.

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

На основании этой формулы можно создать очень короткую программу. И это означает, что в соответствии с алгоритмической теорией π не содержит бесконечного количества информации.

Как видите, в этом конкретном случае алгоритмический подход несколько отличается от предложенного Шенноном, но в большинстве других случаев они согласуются. Например, для передачи случайной последовательности нулей и единиц самой короткой программе необходимо столько же бит, сколько цифр содержится в цепочке.

Возникает вопрос: существует ли число, содержащее бесконечное количество информации по определению Колмогорова и Хайтина (подобное π в определении Шеннона)? Да, такое число существует, и это одно из самых удивительных чисел в истории математики — число омега, известное также как постоянная Хайтина . Ее свойство заключается в том, что эта постоянная не может порождаться кодом, содержащим меньше битов, чем она сама. Это означает, что все биты числа омега полностью случайны.