Не станем спрашивать, остановится ли конкретная программа. Лучше рассмотрим совокупность всех возможных компьютерных программ. Каждой из них придадим определенную вероятность того, что именно ее выберут. Каждый бит информации в случайно выбираемой программе определяется путем подбрасывания монетки, причем для каждого бита этот бросок – независимый. Тогда для программы, содержащей N бит информации, вероятность того, что ее выберут, равна 2>-N. Теперь зададимся вопросом, какова общая вероятность того, что эти программы остановятся. Она, эта вероятность остановки, обозначаемая как «омега» (Ω), позволяет ответить на вопрос Тьюринга о том, остановится ли программа, одним-единственным числом от 0 до 1. Если программа никогда не останавливается, Ω = 0. Если же программа всегда останавливается, Ω = 1.
Точно так же, как компьютеры выражают числа двоичной записью, мы можем выразить «омегу» цепочкой нулей и единиц. Можно ли заранее определить, каким будет N-й бит в этой цепочке цифр – нулем или единицей? Иными словами, можно ли вычислить «омегу»? О нет. Более того, я даже могу показать, что эта последовательность нулей и единиц носит случайный характер. Это можно сделать, используя так называемую алгоритмическую теорию информации, которая приписывает ту или иную степень упорядоченности набору данных в зависимости от того, существует ли алгоритм, способный сжать эти данные, представив их в более краткой форме.
К примеру, цепочку регулярно чередующихся нулей и единиц, описывающую какие-то данные как 0101010101… и состоящую в общей сложности из тысячи знаков, можно сжать в более короткую инструкцию: «Повторить „01“ 500 раз». А вот совершенно случайную цепочку цифр нельзя свести к более короткому тексту-программе. Такие цепочки называют алгоритмически несжимаемыми.
Как показывает мой анализ, вероятность остановки является алгоритмически случайной. Ее нельзя сжать, представив как более короткую инструкцию. Чтобы получить на выходе N бит этого числа, необходимо ввести в компьютер программу длиной по меньшей мере N бит. Каждый из N бит «омеги» – несократимый независимый математический факт, такой же случайный, как и результат подбрасывания монетки. К примеру, в «омеге» столько же нулей, сколько и единиц. Но знание всех ее четных бит не поможет нам узнать никакие из ее нечетных бит.
Мой вывод, что вероятность остановки носит случайный характер, согласуется с утверждением Тьюринга о принципиальной неразрешимости проблемы остановки. Как выясняется, это неплохой пример проявления случайности в теории чисел – этом становом хребте математики.
