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

Постоянную Хайтина можно понимать как вероятность того, что программа, выбранная наугад, остановится. Предположим, что во Вселенной существуют только программы, содержащие три бита информации, то есть всего таких программ восемь: 000, 001, 010, 011, 100, 101, 110, 111. Если бы останавливалась только программа 000, вероятность остановки составила бы 1/8.

Итак, мы можем вычислить вероятность того, что программа, выбранная наугад, остановится, если сложим вероятности выбора всех останавливающихся программ.

Результат будет равен единице, деленной на число программ, содержащих 2 n битов.

Используем для обозначения суммы символ Σ. Постоянная Хайтина в математической нотации записывается следующим образом:

Таким образом, число омега равно вероятности выбора случайной программы, которая остановится, и эта вероятность вычисляется суммированием вероятности выбора всех программ, которые останавливаются.

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

Число омега зависит от используемого языка программирования, так что, строго говоря, следует говорить о постоянных Хайтина — своей для каждого языка. Как мы видим, физическое понятие энтропии порождает математическую дисциплину, теорию информации, которая может быть использована при анализе самых разных ситуаций. Уточнение этого понятия ведет к открытиям, весьма далеким от области физики, но очень важным для чистой математики (например, в работах Хайтина). Впрочем, это обычный путь, которым идет математический прогресс.

* * *

ВЫЧИСЛЯЯ НЕВЫЧИСЛИМОЕ

Хотя постоянные Хайтина и невычислимы, в 2002 году математику Кристиану Калуду(родился в 1952 году) удалось вычислить первые шестьдесят четыре символа для одной из них. Используемый им способ заключался в том, чтобы взять все возможные программы с некоторым числом битов и выяснить, какие из них останавливаются. Вычислять знаки постоянной Хайтина — трудная задача, сложность которой растет с каждым новым знаком после запятой. Если бы в нашем распоряжении были хотя бы первые 10 тысяч битов постоянной Хайтина, мы бы находились на удивительном уровне развития математического знания. Хайтин даже утверждал, что количество знаков числа омега, известных цивилизации, — хорошая мера ее интеллектуального прогресса.

* * *

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

Найти ответ на вопрос можно, рассмотрев микросостояния. Если у газа всего два возможных микросостояния, одного бита достаточно, чтобы определить, в каком из них он находится: ноль для первого, единица для второго. Но если у газа 100 тысяч микросостояний, количество информации равно наиболее близкой степени числа два, которая определяет число битов, необходимых для выбора одного из них.

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

Например, мы можем задуматься, каково максимальное количество информации, которое может храниться в определенном объеме. Это открыло бы нам путь к законам, управляющим Вселенной: если количество информации на единицу объема конечно, то Вселенная, вероятно, дискретна, то есть существует минимальная единица длины, и невозможно разделить пространство на меньшие.