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