Условия, которым удовлетворяют решения уравнения Матиясевича, согласуются с условиями гипотезы JR. Следовательно, мы можем говорить уже не о гипотезе, а о доказанной теореме. Неуловимое множество JR было найдено, следовательно, десятая проблема Гильберта решена: искомого чудесного алгоритма не существует.
Таким образом, путем невероятных умственных усилий удалось доказать: не существует алгоритма, позволяющего определить, имеет ли решение произвольное диофантово уравнение. Всегда найдется уравнение, перед которым спасует любой алгоритм.
Решение десятой проблемы Гильберта основано на тонком различии между перечислимым и вычислимым множеством. Матиясевич, Робинсон, Дэвис и Патнем доказали прекрасный и удивительный результат:
Множество является перечислимым (рекурсивно перечислимым) тогда и только тогда, когда оно является диофантовым.
Однако суть проблемы Гильберта заключается в том, что не все перечислимые множества являются вычислимыми. Достаточно найти одно-единственное перечислимое, но не вычислимое множество, чтобы дело приняло совершенно иной оборот. Это множество будет диофантовым, но соответствующее диофантово уравнение нельзя будет решить никаким алгоритмом.
* * *
УРАВНЕНИЕ ПЕЛЛЯ
Английский математик Джон Пелль (1611–1685) вошел в историю благодаря уравнению, носящему его имя:
x>2 — d(y + 1)>2 = 1.
Это уравнение имеет целые решения тогда и только тогда, когда d не является квадратом. Согласно определениям, приведенным во врезке, посвященной машине Тьюринга, множество чисел, которые не являются квадратами, D = {2, 3, 5, 6, 7, 8, 10…}, является диофантовым.
* * *
Жизнь после десятой проблемы
На день рождения Джулия получила торт с зажженными свечками, задула их и загадала свое обычное желание: дожить до того дня, когда будет найдено решение проклятой проблемы под номером 10, и не важно, кто его найдет и каким будет ответ — положительным или отрицательным. Пока Джулия Робинсон ожидала решения десятой проблемы Гильберта, она успела получить множество почетных наград. Крупнейшей в денежном выражении стала стипендия фонда МакАртура, присужденная ей в 1983 году сроком на пять лет и составлявшая 60 тысяч долларов.
Джулия Робинсон, среди прочего, стала первой женщиной-математиком, принятой в члены Национальной академии наук США (1975), и первой женщиной — президентом Американского математического общества (1978). Для любого американского математика подобный пост является вершиной карьеры, однако он подразумевает определенные обязанности. Прежде чем принять назначение, Джулия посоветовалась с друзьями и родственниками и пришла к выводу, что не имеет морального права отказаться. По крайней мере, эта должность позволила ей лично встретиться на Западе, в Калгари (1982), с Юрием Матиясевичем (они познакомились еще в Советском Союзе) — советские бюрократы ревностно контролировали все заграничные командировки и выпускали советских граждан за границу очень редко и только туда, куда разрешала непредсказуемая логика партии. Во время визита Джулии в СССР математик