Шрифт:
где m и n — целые числа. Такие тройки чисел называются пифагоровыми и известны уже много веков. Намного интереснее выглядят тройки ненулевых чисел х, у, z, когда выполняется условие
хn + уn = zn, n > 2.
В этом случае указанное диофантово уравнение не имеет решений. Так формулируется знаменитая теорема Ферма, доказанная в 1995 году. Десятая проблема Гильберта была не столь «простой» и звучала принципиально иначе: в ней требовалось найти алгоритм, позволяющий определить, имеет ли решения произвольное диофантово уравнение. К счастью, сегодня мы знаем, что такого алгоритма не существует. Для решения десятой проблемы Гильберта потребовалось не 300 лет, как на доказательство теоремы Ферма, но целых 70, а также ряд блестящих идей.
В 1961 году, когда Джулии было чуть за 40, прогнозы врачей подтвердились: ей потребовалась операция на сердце. К счастью, кардиохирургия в те годы была уже достаточно развитой, и лечение прошло успешно. Однако сердце Джулии было слишком слабым, и ей нельзя было перенапрягаться. В результате, когда в 1976 году она стала профессором Калифорнийского университета в Беркли, руководству пришлось согласиться с тем, что преподавать Джулия будет всего на четверть ставки. После операции Джулии порекомендовали езду на велосипеде, и она отдалась этому занятию с такой страстью, что стала покупать велосипеды один за другим, стремясь найти самый легкий и управляемый. Ее муж жаловался: «Другие жены покупают пальто или бриллиантовые браслеты, а моя жена покупает велосипеды».
В 1984 году у Джулии Робинсон обнаружили лейкемию. Благодаря лечению болезнь отступила, но ненадолго: исследовательница умерла в 1985 году.
Десятая проблема Гильберта
На математическом конгрессе 1900 года Давид Гильберт, ведущий математик мира, представил список из 23 нерешенных задач. Решение этих задач, по его мнению, означало бы существенное развитие математики. Гильберт предполагал (для тех времен такая точка зрения была вполне логичной), что любая проблема имеет решение, и рано или поздно все 23 его проблемы будут решены. Сегодня нам известно, что Гильберт ошибался: спустя много лет Курт Гёдель доказал, что существуют задачи, парадоксальным образом не имеющие решения. Между прочим, одной из подобных неразрешимых проблем оказалась континуум-гипотеза — первая же проблема в списке Гильберта. Вне зависимости от того, будем мы считать континуум-гипотезу истинной или ложной, в рамках формальной логики мы никогда не придем к какому-либо противоречию.
Диофантовыми называются полиномиальные уравнения вида
Р(х1, х2, …, хn) = 0
с решениями и коэффициентами на множестве
ax ± by = с,
но не уравнения произвольного вида (указанные уравнения имеют решения тогда и только тогда, когда НОД (а, Ь) является делителем с). Путь к решению десятой проблемы Гильберта непрост, и многие не сразу поймут его. Но мы все же попытаемся описать ее решение, пусть и очень поверхностно.
В 1950 году Джулия Робинсон, применив некоторые свойства уравнения Пелля, не смогла доказать, что определенное числовое множество, которое мы обозначим JR в честь Джулии Робинсон (его нельзя построить, но можно определить в терминах общей арифметики), является диофантовым (см. врезку, посвященную Алану Тьюрингу), но не вычислимым. Множество JR обладало некоторыми интересными свойствами — в частности, его элементы возрастали по экспоненциальному закону.
Доказать указанное свойство не удалось, однако эта гипотеза с высокой вероятностью считалась истинной. Далее будем называть эту гипотезу гипотезой 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.