Однако суть проблемы Гильберта заключается в том, что не все перечислимые множества являются вычислимыми. Достаточно найти одно-единственное перечислимое, но не вычислимое множество, чтобы дело приняло совершенно иной оборот. Это множество будет диофантовым, но соответствующее диофантово уравнение нельзя будет решить никаким алгоритмом.
* * *
УРАВНЕНИЕ ПЕЛЛЯ
Английский математик Джон Пелль (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) заметил, что она — второй по популярности Робинсон в Советском Союзе; первым был Робинзон Крузо. Разумеется, Юрий Матиясевич и Джулия Робинсон могли переписываться и публиковать совместные статьи, ведь, как известно, в единстве сила, а расстояние во много тысяч километров не было для них преградой.
* * *
«ЗОЛОТОЙ РЕБЕНОК» ЮРИЙ МАТИЯСЕВИЧ (Р. 1947 Г.)
Нет никаких сомнений, что Юрий Матиясевич был одаренным ребенком. В 17 лет он стал победителем математической олимпиады, проходившей не где-нибудь, а в Москве. Он является почетным доктором многих университетов и членом различных академий наук, однако для математиков все эти регалии не имеют особого значения. Для них важно, что Матиясевич внес основной вклад в решение десятой проблемы Гильберта, в теории графов его именем назван полином, а его число Эрдёша равно 2. Матиясевич заинтересовался десятой проблемой Гильберта в 1965 году, в 18 лет, спустя всего год после поступления в университет.
В 22 года он нашел ее решение, что стало большим событием в мире математики. Джулия Робинсон писала в письме Матиясевичу: «Теперь, когда я знаю, что это правда, все это кажется мне прекрасным и удивительным. Если тебе в самом деле всего 22 года, мне доставляет особое удовольствие думать, что когда я сформулировала свою гипотезу, ты был еще ребенком, и мне следовало лишь дождаться, пока ты подрастешь».
Юрий Матиясевич в 1969 году, когда он нашел решение десятой проблемы Гильберта.
Представить себе ход мыслей Матиясевича непросто. Приведем всего один элементарный пример, который Юрий Матиясевич предложил в юности, когда ему было всего 24 года, вместе с Сергеем Стечкиным (1920–1995). Постройте параболу так, как показано на иллюстрации. Сделать это очень просто, но на всякий случай укажем, что эта парабола описывается уравнением у = х2. Обозначьте на ней точки с ординатами 2, 3, 4, 5, 6 и так далее. Соедините верхние точки с нижними.
Что общего будет у всех точек, отмеченных на горизонтальной оси? Их координатами будут простые числа. Через эти точки не проходит ни одна прямая. Это построение, которое можно назвать математической игрой, называется решетом Матиясевича — Стечкина и доступно любому старшекласснику, но у всякого любителя математики при его виде перехватит дыхание. Таков Юрий Матиясевич.