Все это выросло из впечатляющих событий 1980-х, когда Джеймс Джонс из Университета Калгари и Юрий Матиясевич из ленинградского Математического института им. Стеклова обнаружили теорему, доказанную французским математиком Франсуа Эдуардом Люка столетием раньше. Теорема, по сути, дает целочисленный метод преобразования универсальной машины Тьюринга в универсальное диофантово уравнение, эквивалентное компьютеру «общего назначения».
Я решил: забавно будет это расписать. И при помощи большого компьютера записал такое вот уравнение универсальной машины Тьюринга. В нем оказалось 17 тысяч переменных, и оно растянулось на 200 страниц.
Эта штука принадлежит к разновидности так называемых экспоненциальных диофантовых уравнений. Все переменные и константы в нем – неотрицательные целые числа: 0, 1, 2, 3, 4, 5 и т. д. Оно называется экспоненциальным, поскольку в нем есть числа, возводимые в целочисленные степени. В нормальных диофантовых уравнениях показатель степени должен быть константой. Здесь же показатель степени может быть переменной. Иными словами, здесь имеется не только x³, но и x>y.
Чтобы преобразовать утверждение о том, что вероятность остановки («омега») носит случайный характер, в утверждение о случайности решений в арифметике, мне требуется внести лишь некоторые небольшие изменения в это двухсотстраничное диофантово уравнение универсальной машины Тьюринга. В результате мое уравнение, носящее случайный характер, также окажется двухсотстраничным. В этом уравнении есть единственный параметр – переменная N. Для каждого конкретного значения этого параметра я задаю вопрос: «Конечное или бесконечное количество целочисленных решений имеет (при данном N) мое уравнение?» Ответ на этот вопрос, как выясняется, эквивалентен расчету вероятности остановки. Этот ответ сообщает на арифметическом языке, каков N-й бит «омеги» – ноль или единица. Если N-й бит «омеги» является нулем, то мое уравнение для данного конкретного значения N имеет конечное количество решений. Если же N-й бит вероятности остановки – единица, то это уравнение для данного значения параметра N имеет бесконечное количество решений. Подобно тому, как N-й бит «омеги» носит случайный характер (это независимый, несократимый факт вроде результата подбрасывания монетки), установление того, конечно или бесконечно количество решений моего уравнения, также носит случайный характер. Точный ответ мы в принципе никогда не сможем узнать.
