Для того чтобы понять, что такое постоянная Хайтина, поговорим о проблеме остановки, которая заключается в том, чтобы определить, остановится ли какая-либо программа. Так, мы знаем, что программа, вычисляющая 2 + 2, остановится, как только будет найдена требуемая сумма. Но точно так же программа, вычисляющая все простые числа, не остановится никогда. Можно доказать, что способа решить проблему остановки для любой программы не существует: мы можем узнать, остановится ли какая-то конкретная программа, но не можем сделать этого для любого алгоритма.
Например, представим себе программу, которой даны инструкции остановиться при нахождении четного числа, которое не может быть выражено как сумма двух простых. Программа остановится, если существует четное число с такими характеристиками, и никогда не остановится в противном случае. Ни один математик до сих пор не смог найти ответ на эту проблему, связанную с доказательством гипотезы Гольдбаха, в которой утверждается, что любое четное число может быть выражено как сумма двух простых чисел. Сегодня кажется, что гипотеза верна — по крайней мере, уже полученные результаты вычислений вполне ей соответствуют, но не доказано, что эта тенденция сохранится до бесконечности.
Постоянную Хайтина можно понимать как вероятность того, что программа, выбранная наугад, остановится. Предположим, что во Вселенной существуют только программы, содержащие три бита информации, то есть всего таких программ восемь: 000, 001, 010, 011, 100, 101, 110, 111. Если бы останавливалась только программа 000, вероятность остановки составила бы 1/8.
Итак, мы можем вычислить вероятность того, что программа, выбранная наугад, остановится, если сложим вероятности выбора всех останавливающихся программ.
Результат будет равен единице, деленной на число программ, содержащих 2n битов.
Используем для обозначения суммы символ Σ. Постоянная Хайтина в математической нотации записывается следующим образом:
Таким образом, число омега равно вероятности выбора случайной программы, которая остановится, и эта вероятность вычисляется суммированием вероятности выбора всех программ, которые останавливаются.
Число Хайтина имеет любопытные математические свойства. С одной стороны, его невозможно вычислить, поскольку для этого потребовалась бы программа с бесконечным числом битов. Также это число случайно, ведь если бы это было не так, можно было бы сжать содержащуюся в нем информацию и вычислить эту постоянную. Но самое важное — это то, что вычисление постоянной Хайтина позволяет решить проблему остановки для любой программы. Поскольку подавляющее большинство нерешенных математических задач можно свести к вопросу о том, остановится ли программа, знание постоянной Хайтина равносильно владению всем математическим знанием Вселенной.
Число омега зависит от используемого языка программирования, так что, строго говоря, следует говорить о постоянных Хайтина — своей для каждого языка. Как мы видим, физическое понятие энтропии порождает математическую дисциплину, теорию информации, которая может быть использована при анализе самых разных ситуаций. Уточнение этого понятия ведет к открытиям, весьма далеким от области физики, но очень важным для чистой математики (например, в работах Хайтина). Впрочем, это обычный путь, которым идет математический прогресс.
* * *
ВЫЧИСЛЯЯ НЕВЫЧИСЛИМОЕ
Хотя постоянные Хайтина и невычислимы, в 2002 году математику Кристиану Калуду (родился в 1952 году) удалось вычислить первые шестьдесят четыре символа для одной из них. Используемый им способ заключался в том, чтобы взять все возможные программы с некоторым числом битов и выяснить, какие из них останавливаются. Вычислять знаки постоянной Хайтина — трудная задача, сложность которой растет с каждым новым знаком после запятой. Если бы в нашем распоряжении были хотя бы первые 10 тысяч битов постоянной Хайтина, мы бы находились на удивительном уровне развития математического знания. Хайтин даже утверждал, что количество знаков числа омега, известных цивилизации, — хорошая мера ее интеллектуального прогресса.
* * *