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