Том 42. Путешествие от частицы до Вселенной. Математика газовой динамики | страница 66
Применим алгоритмическое определение информации к вычислению знаков числа π. Вспомним, что, согласно Шеннону, количество информации, содержащейся в числе π, бесконечно. Однако существует простая формула, которая позволяет довольно точно вычислить знаки этого числа. Выглядит она следующим образом:
На основании этой формулы можно создать очень короткую программу. И это означает, что в соответствии с алгоритмической теорией π не содержит бесконечного количества информации.
Как видите, в этом конкретном случае алгоритмический подход несколько отличается от предложенного Шенноном, но в большинстве других случаев они согласуются. Например, для передачи случайной последовательности нулей и единиц самой короткой программе необходимо столько же бит, сколько цифр содержится в цепочке.
Возникает вопрос: существует ли число, содержащее бесконечное количество информации по определению Колмогорова и Хайтина (подобное π в определении Шеннона)? Да, такое число существует, и это одно из самых удивительных чисел в истории математики — число омега, известное также как постоянная Хайтина. Ее свойство заключается в том, что эта постоянная не может порождаться кодом, содержащим меньше битов, чем она сама. Это означает, что все биты числа омега полностью случайны.
Для того чтобы понять, что такое постоянная Хайтина, поговорим о проблеме остановки, которая заключается в том, чтобы определить, остановится ли какая-либо программа. Так, мы знаем, что программа, вычисляющая 2 + 2, остановится, как только будет найдена требуемая сумма. Но точно так же программа, вычисляющая все простые числа, не остановится никогда. Можно доказать, что способа решить проблему остановки для любой программы не существует: мы можем узнать, остановится ли какая-то конкретная программа, но не можем сделать этого для любого алгоритма.
Например, представим себе программу, которой даны инструкции остановиться при нахождении четного числа, которое не может быть выражено как сумма двух простых. Программа остановится, если существует четное число с такими характеристиками, и никогда не остановится в противном случае. Ни один математик до сих пор не смог найти ответ на эту проблему, связанную с доказательством гипотезы Гольдбаха, в которой утверждается, что любое четное число может быть выражено как сумма двух простых чисел. Сегодня кажется, что гипотеза верна — по крайней мере, уже полученные результаты вычислений вполне ей соответствуют, но не доказано, что эта тенденция сохранится до бесконечности.
