Женщины-математики. От Гипатии до Эмми Нётер

В 1946 году она получила степень доктора под руководством выдающегося математика Альфреда Тарского (1902–1983), защитив диссертацию о проблемах разрешимости в арифметике рациональных чисел (Definability and Decision Problems in Arithmetic). Джулия столкнулась с подобными проблемами впервые, и, по всей видимости, они произвели на нее неизгладимое впечатление. Именно Тарский первым заговорил с подопечной о диофантовых уравнениях.

За исключением всего двух важных статей, все математические труды Джулии Робинсон касались десятой проблемы Гильберта (о ней мы более подробно поговорим далее) и проблем разрешимости. Первая из этих двух статей (A Note on Exact Sequential Analysis) была посвящена аналитико-статистической задаче и написана в период совместной работы с Нейманом. Во второй статье, опубликованной в 1951 году, во время короткого периода работы в корпорации RAND (ведущем американском мозговом центре), рассматривалось решение проблемы равновесия Нэша в теории игр, в то время находившейся на пике популярности, называлась эта работа «Итеративный метод решения игр» (An Iterative Method of Solving a Game).

Как видите, Джулия Робинсон и диофантовы уравнения были словно созданы друг для друга.

Диофантово уравнение — это уравнение с одной или несколькими неизвестными с целыми коэффициентами, решения которого принадлежат множеству целых чисел

. Эти уравнения названы в честь древнегреческого математика Диофанта Александрийского (ок. 200–214 — ок. 284–298), который посвятил им целый трактат — «Арифметику». Примером диофантового уравнения является уравнение с тремя неизвестными

х² + у² = z².

Как вы знаете, это уравнение выражает теорему Пифагора, и еще с глубокой древности известно, что оно имеет бесконечно много решений. В параметрическом виде решениями этого уравнения являются тройки чисел вида:

х = m² — n²,

у = 2mn,

z = m² + n²,

где m и n — целые числа. Такие тройки чисел называются пифагоровыми и известны уже много веков. Намного интереснее выглядят тройки ненулевых чисел х, у, z, когда выполняется условие

хⁿ + уⁿ = zⁿ, n > 2.

В этом случае указанное диофантово уравнение не имеет решений. Так формулируется знаменитая теорема Ферма, доказанная в 1995 году. Десятая проблема Гильберта была не столь «простой» и звучала принципиально иначе: в ней требовалось найти алгоритм, позволяющий определить, имеет ли решения произвольное диофантово уравнение. К счастью, сегодня мы знаем, что такого алгоритма не существует. Для решения десятой проблемы Гильберта потребовалось не 300 лет, как на доказательство теоремы Ферма, но целых 70, а также ряд блестящих идей.

В 1961 году, когда Джулии было чуть за 40, прогнозы врачей подтвердились: ей потребовалась операция на сердце. К счастью, кардиохирургия в те годы была уже достаточно развитой, и лечение прошло успешно. Однако сердце Джулии было слишком слабым, и ей нельзя было перенапрягаться. В результате, когда в 1976 году она стала профессором Калифорнийского университета в Беркли, руководству пришлось согласиться с тем, что преподавать Джулия будет всего на четверть ставки. После операции Джулии порекомендовали езду на велосипеде, и она отдалась этому занятию с такой страстью, что стала покупать велосипеды один за другим, стремясь найти самый легкий и управляемый. Ее муж жаловался: «Другие жены покупают пальто или бриллиантовые браслеты, а моя жена покупает велосипеды».

В 1984 году у Джулии Робинсон обнаружили лейкемию. Благодаря лечению болезнь отступила, но ненадолго: исследовательница умерла в 1985 году.

Десятая проблема Гильберта

На математическом конгрессе 1900 года Давид Гильберт, ведущий математик мира, представил список из 23 нерешенных задач. Решение этих задач, по его мнению, означало бы существенное развитие математики. Гильберт предполагал (для тех времен такая точка зрения была вполне логичной), что любая проблема имеет решение, и рано или поздно все 23 его проблемы будут решены. Сегодня нам известно, что Гильберт ошибался: спустя много лет Курт Гёдель доказал, что существуют задачи, парадоксальным образом не имеющие решения. Между прочим, одной из подобных неразрешимых проблем оказалась континуум-гипотеза — первая же проблема в списке Гильберта. Вне зависимости от того, будем мы считать континуум-гипотезу истинной или ложной, в рамках формальной логики мы никогда не придем к какому-либо противоречию.

Диофантовыми называются полиномиальные уравнения вида

Р(х₁, х₂, …, х_n) = 0

с решениями и коэффициентами на множестве

. Проблема Гильберта под номером 10 звучала так: существует ли алгоритм или метод, позволяющий определить, имеет ли решения произвольное диофантово уравнение? В конце концов в 1970 году было доказано, что такого алгоритма не существует. Десятая проблема Гильберта допускает бесконечное множество случаев. Известны подмножества случаев, для которых искомый спасительный алгоритм существует, однако в задаче требуется найти универсальный алгоритм для всех возможных случаев. К примеру, алгоритм Евклида позволяет решить диофантовы уравнения вида

ax ± by = с,

но не уравнения произвольного вида (указанные уравнения имеют решения тогда и только тогда, когда НОД (а, Ь) является делителем с). Путь к решению десятой проблемы Гильберта непрост, и многие не сразу поймут его. Но мы все же попытаемся описать ее решение, пусть и очень поверхностно.

В 1950 году Джулия Робинсон, применив некоторые свойства уравнения Пелля, не смогла доказать, что определенное числовое множество, которое мы обозначим JR в честь Джулии Робинсон (его нельзя построить, но можно определить в терминах общей арифметики), является диофантовым (см. врезку, посвященную Алану Тьюрингу), но не вычислимым. Множество JR обладало некоторыми интересными свойствами — в частности, его элементы возрастали по экспоненциальному закону.

Доказать указанное свойство не удалось, однако эта гипотеза с высокой вероятностью считалась истинной. Далее будем называть эту гипотезу гипотезой JR. В 1959 году Мартин Дэвис и Хилари Патнем доказали, что при определенных условиях из гипотезы JR следует очень важный результат: любое рекурсивно перечислимое множество является диофантовым. Если выполняются начальные условия и гипотеза JR, то десятую проблему Гильберта можно считать решенной, и ответ на нее будет отрицательным.

* * *

НЕМНОГО ТЬЮРИНГА

При решении проблем разрешимости и вычислимости, а также логических задач обычно используются машины Тьюринга. Эти машины, придуманные английским ученым Аланом Тьюрингом (1912–1954), в действительности представляют собой идеальные математические абстракции вычислительных машин с бесконечной памятью. Представьте себе ящик с входным и выходным отверстиями, через которые проходит бумажная лента, разделенная на прямоугольные ячейки. В каждой ячейке записана цифра — 0 или 1. В крышке ящика есть смотровое отверстие, через которое в любой момент можно увидеть, какая цифра записана в ячейку. На каждом шаге цифру в ячейке можно заменить на 0 или 1. Аналогично, можно определить, куда следует переместить считывающее устройство на следующем шаге: влево или вправо. Новая записанная цифра и новое состояние машины зависят от текущего состояния машины, а следующий шаг (и следующее состояние) указаны в программе, записанной в управляющем устройстве. Программы различных машин Тьюринга отличаются. Прекратит ли машина работу, зависит оттого, что указано в программе. Может показаться, что от столь простого устройства не стоит ждать многого, однако потенциал машины Тьюринга огромен.

Простейшая схема работы машины Тьюринга.

Далее приведены три определения, тесно связанные с работами Джулии Робинсон и диофантовыми уравнениями. Они приводятся отдельно, так как используются в рассуждениях, самих по себе достаточно сложных.

— Перечислимое множество (по историческим причинам также называется рекурсивно перечислимым): множество целых чисел L называется перечислимым, если существует машина Тьюринга такая, что если ввести в нее целое число, она остановится на 1, если указанное число принадлежит L Если указанное целое число не принадлежит L, машина может остановиться на 0 или не остановиться никогда.

— Вычислимое множество: множество С называется вычислимым, если существует программа машины Тьюринга такая, что для любого введенного целого числа машина останавливается на 1, если это число принадлежит С, в противном случае — на 0. Чуть менее понятное, но эквивалентное определение вычислимого множества таково: множество С называется вычислимым тогда и только тогда, когда С и его дополнение С^–  являются перечислимыми. Очевидно, что любое вычислимое множество является перечислимым, но не наоборот.

— Диофантово множество: множество целых чисел D называется диофантовым, если его можно определить с помощью многочлена Р (x₁, x₂, x_t) от переменных d, t, x₁, x₂…., x_t >= 1 с целыми коэффициентами такого, что Р обращается в ноль при присвоении целых значений x₁, x₂…., x_t тогда и только тогда, когда d равно одному из элементов множества D.