Дэвис, Мартин (математик)

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Мартин Дэвис
Martin Davis.jpg
Дата рождения:

1928[1]

Место рождения:
Страна:
Научная сфера:

теория чисел

Альма-матер:
Научный руководитель:

Алонзо Чёрч

Награды и премии:
Commons-logo.svg Мартин Дэвис на Викискладе

Мартин Дэвид Дэвис (англ. Martin Davis, род. 1928 год) — американский математик, известный своей работой, которая посвящена десятой проблеме Гильберта[2][3].

Биография[править | править вики-текст]

Родители Дэвиса иммигрировали в США из города Лодзь (Польша). Встретившись уже в Нью-Йорке, они поженились. Дэвис родился и вырос в городе Бронкс. Родители с детства поощряли Мартина получить высшее образование[2][3].

В 1950 году под руководством Алонзо Черча Мартин получил доктора в Принстонском университете, который является одним из старейших и самых престижных университетов США.

Взнос[править | править вики-текст]

Дэвис — один из изобретателей алгоритма Дэвиса-Путнама[en] и алгоритма DPLL. Также он известен благодаря своей модели машины Поста.

Десятая проблема Гильберта[править | править вики-текст]

В 30-х годах ХХ века формализуется понятие алгоритм, а также появляются первые примеры алгоритмически неразрешимых теорий в математической логике. Важным моментом стало доказательство Андреем Марковым и Эмилем Постом (независимо друг от друга) неразрешимость задачи Туе[en][4] в 1947 году. Это было первое доказательство неразрешимости алгебраической задачи. Трудности, с которыми столкнулись исследователи диофантовых уравнений, вызвали предположение, что необходимого Гильбертом алгоритма не существует. Немного ранее, в 1944 году, Эмиль Пост в одной из своих работ уже писал, что десятая проблема «молит о доказательстве неразрешимости» (англ. «Begs for an unsolvability proof»).

Гипотеза Дэвиса[править | править вики-текст]

Слова Поста вдохновили студента Мартина Дэвиса на поиск доказательств неразрешимости десятой проблемы. Дэвис перешел от ее формулировки в целых числах к более естественной для теории алгоритмов формулировки в натуральных числах. Это две разные задачи, однако каждая из них сводится к другой. В 1953 году он опубликовал работу, в которой наметил путь решения десятой проблемы в натуральных числах.

Дэвис наравне с классическими диофантовыми уравнениями рассмотрел их параметрическую версию:

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

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

Понятие диофантового и перечислимого множества совпадают. Это значит, что множество диофантово тогда и только тогда, когда оно перечислимое.

Дэвис также сделал первый шаг — доказал, что любое перечислимое множество можно представить в виде:

Это получило название «нормальная форма Дэвиса». Доказать свою гипотезу, избавившись от квантора всеобщности, ему на тот момент не удалось.

Награды и почетные звания[править | править вики-текст]

В 1975 году, Дэвис был награжден премией Стила, премией «Chauvenet Prize» и премией Лестера Форда за работу, которая посвящена десятой проблеме Гильберта[3].

В 1982 году Мартин стал членом и Американской академии искусств и наук[3].

В 2012 был избран стипендиатом Американского математического общества[5].

Отдельные издания[править | править вики-текст]

Книги
  • Мартин Дэвис. Прикладной нестандартный анализ. — Нью-Йорк: Wiley, 1977. — ISBN 9780471198970.
  • Вычислимости, сложность и речи: Основы теоретической информатики. — 2-й том. — Бостон: Academic Press, Harcourt, Brace, 1994. — ISBN 9780122063824.
  • Мартин Дэвис. Двигатели логики: математика и происхождение компьютера. — Нью-Йорк: Norton, 2000. — ISBN 9780393322293.
Обзор «двигателей логики»: Уоллес, Ричард, Математики которые забывают ошибки истории: обзор двигателей логики("'Мартин Дэвис"'), ALICE A. I. Foundation, <http://www.alicebot.org/articles/wallace/mathematicia..> 
Статьи
  • Мартин Дэвис (1995), «есть Ли математическая интуиция алгоритмическом», «Поведенческие и мозговые науки», «'13»'(4), 659-60.

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

Ссылки[править | править вики-текст]