Джулия Робинсон: Жизнь и вклад в теорию вычислимости

Введение

Джулия Холл Боуман Робинсон (англ. Julia Hall Bowman Robinson; 8 декабря 1919 – 30 июля 1985) – американский математик, известная своими вкладами в теорию вычислимости и теорию вычислительной сложности, в особенности в области задач о разрешимости. Ее работа над десятой проблемой Гильберта (ныне известной как теорема Матиясевича или теорема MRDP) сыграла решающую роль в ее окончательном решении. В 1983 году Робинсон была удостоена стипендии фонда МакАртура.

Ранние годы

Робинсон родилась в Сент-Луисе, штат Миссури, в семье Ральфа Боуэрса Боумена и Хелен (Холл) Боуман. Это привело к тому, что она пропустила два года учёбы в школе. Когда она поправилась, её обучал частный репетитор – отставной учитель начальной школы. Всего за один год она освоила программу пятого, шестого, седьмого и восьмого классов. Среди курсов был курс теории чисел, который вел Рафаэль М. Робинсон. Она получила степень бакалавра в 1940 году.

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

Десятая задача Гильберта ставит вопрос о существовании алгоритма для определения, имеет ли диофантово уравнение какие-либо целочисленные решения. Робинсон начала исследовать методы решения этой проблемы в 1948 году, работая в корпорации RAND. Ее работа, касающаяся диофантового представления возведения в степень, и ее метод использования уравнения Пелля привели к гипотезе J. R. (названной в честь Робинсона) в 1950 году. Доказательство этой гипотезы стало бы ключевым в конечном решении. Ее исследовательские публикации привели к сотрудничеству с Мартином Дэвисом, Хилари Путнамом и Юрием Матиясевичем. В 1950 году Робинсон впервые встретила Мартина Дэвиса, тогда преподавателя в Университете Иллинойса в Урбана-Шампейне, который пытался доказать, что все множества со свойством перечислимости являются диофантовыми, в отличие от попытки Робинсон показать, что некоторые специальные множества – включая простые числа и степени 2 – являются диофантовыми. Робинсон и Дэвис начали сотрудничать в 1959 году, а позже к ним присоединился Хилари Путнам. Им удалось показать, что решения уравнения, которое можно назвать "золотой серединой", являются ключом к десятой проблеме Гильберта. В 1970 году проблема была решена отрицательно, то есть было показано, что такого алгоритма не существует. В 1970-х годах Робинсон продолжала работать с Матиясевичем над одним из следствий их решения, о котором она однажды заявила, что существует константа N, такая, что для любого диофантового уравнения с любым числом параметров и неизвестных можно эффективно преобразовать это уравнение в другое с теми же параметрами, но только с N неизвестными, причем оба уравнения будут либо разрешимы, либо неразрешимы при одних и тех же значениях параметров. Когда решение было впервые опубликовано, авторы установили N = 200. Совместная работа Робинсона и Матиясевича привела к дальнейшему сокращению до 9 неизвестных. Это была первая публикация, в которой использовалось выражение "задача коммивояжера". Вскоре после этого, в 1951 году, она опубликовала статью под названием "Итеративный метод решения игры". В этой статье она доказала, что динамика вымышленной игры сходится к равновесию Нэша в смешанных стратегиях в двух игровых играх с нулевой суммой. Джордж В. Браун предложил это как призовую задачу в корпорации RAND. Альфред Тарски и Ежи Нейман также прилетели в Вашингтон, округ Колумбия, чтобы более подробно объяснить Национальной академии наук, почему ее работа так важна и как она внесла огромный вклад в математику. Ей потребовалось время, чтобы принять номинацию, как она написала в своей автобиографии: "В 1982 году меня выдвинули на пост президента Американского математического общества. Я поняла, что меня выбрали, потому что я женщина и потому, что у меня была своего рода печать одобрения Национальной академии. После обсуждения с Рафаэлем, который считал, что мне следует отказаться и сохранить энергию для математики, и другими членами моей семьи, которые с ним не согласились, я решила, что как женщина и математик у меня нет другого выбора, кроме как принять. Я всегда старалась делать все возможное, чтобы поощрять талантливых женщин становиться научными математиками. Я нашла свою работу в качестве президента Общества утомительной, но очень, очень полезной". Примерно в это же время она также получила стипендию Макартура в размере 60 000 долларов. В 1985 году она также стала членом Американской академии искусств и наук.

Hilbert's tenth problem asks for an algorithm to determine whether a Diophantine equation has any solutions in integers. Robinson began exploring methods for this problem in 1948 while at the RAND Corporation. Her work regarding Diophantine representation for exponentiation and her method of using Pell's equation led to the J. R. hypothesis (named after Robinson) in 1950. Proving this hypothesis would be central in the eventual solution. Her research publications would lead to collaborations with Martin Davis, Hilary Putnam, and Yuri Matiyasevich. In 1950, Robinson first met Martin Davis, then an instructor at the University of Illinois at Urbana Champaign, who was trying to show that all sets with listability property were Diophantine in contrast to Robinson's attempt to show that a few special sets—including prime numbers and the powers of 2—were Diophantine. Robinson and Davis started collaborating in 1959 and were later joined by Hilary Putnam, they then showed that the solutions to a “Goldilocks” equation was key to Hilbert's tenth problem. In 1970, the problem was resolved in the negative; that is, they showed that no such algorithm can exist. Through the 1970s, Robinson continued working with Matiyasevich on one of their solution's corollaries, which she once stated that

there is a constant N such that, given a Diophantine equation with any number of parameters and in any number of unknowns, one can effectively transform this equation into another with the same parameters but in only N unknowns such that both equations are solvable or unsolvable for the same values of the parameters. At the time the solution was first published, the authors established N = 200. Robinson and Matiyasevich's joint work would produce further reduction to 9 unknowns. is the first publication to use the phrase "travelling salesman problem". Shortly thereafter she published a paper called "An Iterative Method of Solving a Game" in 1951. In her paper, she proved that the fictitious play dynamics converges to the mixed strategy Nash equilibrium in two player zero sum games. This was posed by George W. Brown as a prize problem at RAND Corporation. Alfred Tarski and Jerzy Neyman also flew out to Washington, D. C. to further explain to the National Academy of Sciences why her work is so important and how it tremendously contributed to mathematics. It took time for her to accept the nomination, as stated in her autobiography:<blockquote>"In 1982 I was nominated for the presidency of the American Mathematical Society. I realized that I had been chosen because I was a woman and because I had the seal of approval, as it were, of the National Academy. After discussion with Raphael, who thought I should decline and save my energy for mathematics, and other members of my family, who differed with him, I decided that as a woman and a mathematician I had no alternative but to accept. I have always tried to do everything I could to encourage talented women to become research mathematicians. I found my service as president of the Society taxing but very, very satisfying." Around this time she also was given the MacArthur Fellowship prize of $60,000. In 1985, she also became a member of the American Academy of Arts and Sciences.