Шанс есть! Наука удачи, случайности и вероятности

Не станем спрашивать, остановится ли конкретная программа. Лучше рассмотрим совокупность всех возможных компьютерных программ. Каждой из них придадим определенную вероятность того, что именно ее выберут. Каждый бит информации в случайно выбираемой программе определяется путем подбрасывания монетки, причем для каждого бита этот бросок – независимый. Тогда для программы, содержащей N бит информации, вероятность того, что ее выберут, равна 2^-N. Теперь зададимся вопросом, какова общая вероятность того, что эти программы остановятся. Она, эта вероятность остановки, обозначаемая как «омега» (Ω), позволяет ответить на вопрос Тьюринга о том, остановится ли программа, одним-единственным числом от 0 до 1. Если программа никогда не останавливается, Ω = 0. Если же программа всегда останавливается, Ω = 1.

Точно так же, как компьютеры выражают числа двоичной записью, мы можем выразить «омегу» цепочкой нулей и единиц. Можно ли заранее определить, каким будет N-й бит в этой цепочке цифр – нулем или единицей? Иными словами, можно ли вычислить «омегу»? О нет. Более того, я даже могу показать, что эта последовательность нулей и единиц носит случайный характер. Это можно сделать, используя так называемую алгоритмическую теорию информации, которая приписывает ту или иную степень упорядоченности набору данных в зависимости от того, существует ли алгоритм, способный сжать эти данные, представив их в более краткой форме.

К примеру, цепочку регулярно чередующихся нулей и единиц, описывающую какие-то данные как 0101010101… и состоящую в общей сложности из тысячи знаков, можно сжать в более короткую инструкцию: «Повторить „01“ 500 раз». А вот совершенно случайную цепочку цифр нельзя свести к более короткому тексту-программе. Такие цепочки называют алгоритмически несжимаемыми.

Как показывает мой анализ, вероятность остановки является алгоритмически случайной. Ее нельзя сжать, представив как более короткую инструкцию. Чтобы получить на выходе N бит этого числа, необходимо ввести в компьютер программу длиной по меньшей мере N бит. Каждый из N бит «омеги» – несократимый независимый математический факт, такой же случайный, как и результат подбрасывания монетки. К примеру, в «омеге» столько же нулей, сколько и единиц. Но знание всех ее четных бит не поможет нам узнать никакие из ее нечетных бит.

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

Все это выросло из впечатляющих событий 1980-х, когда Джеймс Джонс из Университета Калгари и Юрий Матиясевич из ленинградского Математического института им. Стеклова обнаружили теорему, доказанную французским математиком Франсуа Эдуардом Люка столетием раньше. Теорема, по сути, дает целочисленный метод преобразования универсальной машины Тьюринга в универсальное диофантово уравнение, эквивалентное компьютеру «общего назначения».

Я решил: забавно будет это расписать. И при помощи большого компьютера записал такое вот уравнение универсальной машины Тьюринга. В нем оказалось 17 тысяч переменных, и оно растянулось на 200 страниц.

Эта штука принадлежит к разновидности так называемых экспоненциальных диофантовых уравнений. Все переменные и константы в нем – неотрицательные целые числа: 0, 1, 2, 3, 4, 5 и т. д. Оно называется экспоненциальным, поскольку в нем есть числа, возводимые в целочисленные степени. В нормальных диофантовых уравнениях показатель степени должен быть константой. Здесь же показатель степени может быть переменной. Иными словами, здесь имеется не только x³, но и x^y.

Чтобы преобразовать утверждение о том, что вероятность остановки («омега») носит случайный характер, в утверждение о случайности решений в арифметике, мне требуется внести лишь некоторые небольшие изменения в это двухсотстраничное диофантово уравнение универсальной машины Тьюринга. В результате мое уравнение, носящее случайный характер, также окажется двухсотстраничным. В этом уравнении есть единственный параметр – переменная N. Для каждого конкретного значения этого параметра я задаю вопрос: «Конечное или бесконечное количество целочисленных решений имеет (при данном N) мое уравнение?» Ответ на этот вопрос, как выясняется, эквивалентен расчету вероятности остановки. Этот ответ сообщает на арифметическом языке, каков N-й бит «омеги» – ноль или единица. Если N-й бит «омеги» является нулем, то мое уравнение для данного конкретного значения N имеет конечное количество решений. Если же N-й бит вероятности остановки – единица, то это уравнение для данного значения параметра N имеет бесконечное количество решений. Подобно тому, как N-й бит «омеги» носит случайный характер (это независимый, несократимый факт вроде результата подбрасывания монетки), установление того, конечно или бесконечно количество решений моего уравнения, также носит случайный характер. Точный ответ мы в принципе никогда не сможем узнать.