Доказать указанное свойство не удалось, однако эта гипотеза с высокой вероятностью считалась истинной. Далее будем называть эту гипотезу гипотезой JR. В 1959 году Мартин Дэвис и Хилари Патнем доказали, что при определенных условиях из гипотезы JR следует очень важный результат: любое рекурсивно перечислимое множество является диофантовым. Если выполняются начальные условия и гипотеза JR, то десятую проблему Гильберта можно считать решенной, и ответ на нее будет отрицательным.
* * *
НЕМНОГО ТЬЮРИНГА
При решении проблем разрешимости и вычислимости, а также логических задач обычно используются машины Тьюринга. Эти машины, придуманные английским ученым Аланом Тьюрингом (1912–1954), в действительности представляют собой идеальные математические абстракции вычислительных машин с бесконечной памятью. Представьте себе ящик с входным и выходным отверстиями, через которые проходит бумажная лента, разделенная на прямоугольные ячейки. В каждой ячейке записана цифра — 0 или 1. В крышке ящика есть смотровое отверстие, через которое в любой момент можно увидеть, какая цифра записана в ячейку. На каждом шаге цифру в ячейке можно заменить на 0 или 1. Аналогично, можно определить, куда следует переместить считывающее устройство на следующем шаге: влево или вправо. Новая записанная цифра и новое состояние машины зависят от текущего состояния машины, а следующий шаг (и следующее состояние) указаны в программе, записанной в управляющем устройстве. Программы различных машин Тьюринга отличаются. Прекратит ли машина работу, зависит оттого, что указано в программе. Может показаться, что от столь простого устройства не стоит ждать многого, однако потенциал машины Тьюринга огромен.
Простейшая схема работы машины Тьюринга.
Далее приведены три определения, тесно связанные с работами Джулии Робинсон и диофантовыми уравнениями. Они приводятся отдельно, так как используются в рассуждениях, самих по себе достаточно сложных.
— Перечислимое множество (по историческим причинам также называется рекурсивно перечислимым): множество целых чисел L называется перечислимым, если существует машина Тьюринга такая, что если ввести в нее целое число, она остановится на 1, если указанное число принадлежит L Если указанное целое число не принадлежит L, машина может остановиться на 0 или не остановиться никогда.
— Вычислимое множество: множество С называется вычислимым, если существует программа машины Тьюринга такая, что для любого введенного целого числа машина останавливается на 1, если это число принадлежит С, в противном случае — на 0. Чуть менее понятное, но эквивалентное определение вычислимого множества таково: множество С называется вычислимым тогда и только тогда, когда С и его дополнение С― являются перечислимыми. Очевидно, что любое вычислимое множество является перечислимым, но не наоборот.
— Диофантово множество: множество целых чисел D называется диофантовым, если его можно определить с помощью многочлена Р (x1, x2, xt) от переменных d, t, x1, x2…., xt >= 1 с целыми коэффициентами такого, что Р обращается в ноль при присвоении целых значений x1, x2…., xt тогда и только тогда, когда d равно одному из элементов множества D.
Алан Тьюринг.
* * *
Всего годом позже в игру вступила Джулия Робинсон: ей удалось упростить задачу и устранить неудобные начальные условия, описанные Дэвис и Патнем. Ситуация была такова: если возможно множество вида JR, то десятая проблема Гильберта будет решена. Достаточно найти диофантово уравнение с определенными решениями, возрастающими экспоненциально, но это уравнение ускользало от математиков. Открытие было совершено в 1970 году, спустя почти 30 лет поисков. Юный математик Юрий Матиясевич из Советского Союза представил колоссальную систему диофантовых уравнений:
Если мы возведем обе части всех этих уравнений в квадрат и сложим их почленно, то получим одно уравнение, которое будет иметь те же решения на множестве натуральных чисел, что и вся система. Полученное уравнение будет удовлетворять необходимым начальным условиям.
Матиясевич получил приведенные выше десять уравнений не случайно: он использовал в работе весьма остроумные методы. Ключевую идею математик заимствовал из теоремы, доказанной в 1942 году и затерянной на страницах третьего издания старенькой книжечки под названием «Числа Фибоначчи» советского математика Николая Воробьева. Для десяти приведенных выше уравнений выполняется равенство v = F2 м, где Fi — i-e число Фибоначчи. Интересно, что эта теорема приводится только в третьем издании книги Воробьева и отсутствует в первых двух.
Условия, которым удовлетворяют решения уравнения Матиясевича, согласуются с условиями гипотезы JR. Следовательно, мы можем говорить уже не о гипотезе, а о доказанной теореме. Неуловимое множество JR было найдено, следовательно, десятая проблема Гильберта решена: искомого чудесного алгоритма не существует.
Таким образом, путем невероятных умственных усилий удалось доказать: не существует алгоритма, позволяющего определить, имеет ли решение произвольное диофантово уравнение. Всегда найдется уравнение, перед которым спасует любой алгоритм.
Решение десятой проблемы Гильберта основано на тонком различии между перечислимым и вычислимым множеством. Матиясевич, Робинсон, Дэвис и Патнем доказали прекрасный и удивительный результат:
Множество является перечислимым (рекурсивно перечислимым) тогда и только тогда, когда оно является диофантовым.
Однако суть проблемы Гильберта заключается в том, что не все перечислимые множества являются вычислимыми. Достаточно найти одно-единственное перечислимое, но не вычислимое множество, чтобы дело приняло совершенно иной оборот. Это множество будет диофантовым, но соответствующее диофантово уравнение нельзя будет решить никаким алгоритмом.
* * *
УРАВНЕНИЕ ПЕЛЛЯ
Английский математик Джон Пелль (1611–1685) вошел в историю благодаря уравнению, носящему его имя:
x2 — d(y + 1)2 = 1.
Это уравнение имеет целые решения тогда и только тогда, когда d не является квадратом. Согласно определениям, приведенным во врезке, посвященной машине Тьюринга, множество чисел, которые не являются квадратами, D = {2, 3, 5, 6, 7, 8, 10…}, является диофантовым.
* * *
Жизнь после десятой проблемы
На день рождения Джулия получила торт с зажженными свечками, задула их и загадала свое обычное желание: дожить до того дня, когда будет найдено решение проклятой проблемы под номером 10, и не важно, кто его найдет и каким будет ответ — положительным или отрицательным. Пока Джулия Робинсон ожидала решения десятой проблемы Гильберта, она успела получить множество почетных наград. Крупнейшей в денежном выражении стала стипендия фонда МакАртура, присужденная ей в 1983 году сроком на пять лет и составлявшая 60 тысяч долларов.
Джулия Робинсон, среди прочего, стала первой женщиной-математиком, принятой в члены Национальной академии наук США (1975), и первой женщиной — президентом Американского математического общества (1978). Для любого американского математика подобный пост является вершиной карьеры, однако он подразумевает определенные обязанности. Прежде чем принять назначение, Джулия посоветовалась с друзьями и родственниками и пришла к выводу, что не имеет морального права отказаться. По крайней мере, эта должность позволила ей лично встретиться на Западе, в Калгари (1982), с Юрием Матиясевичем (они познакомились еще в Советском Союзе) — советские бюрократы ревностно контролировали все заграничные командировки и выпускали советских граждан за границу очень редко и только туда, куда разрешала непредсказуемая логика партии. Во время визита Джулии в СССР математик Юрий Линник (1915–1972) заметил, что она — второй по популярности Робинсон в Советском Союзе; первым был Робинзон Крузо. Разумеется, Юрий Матиясевич и Джулия Робинсон могли переписываться и публиковать совместные статьи, ведь, как известно, в единстве сила, а расстояние во много тысяч километров не было для них преградой.
