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