Русская Википедия:Дэвис, Мартин (математик)

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:ФИО Шаблон:Учёный

Мартин Дэвид Дэвис (Шаблон:Lang-en, 8 марта 1928 — 1 января 2023) — американский Шаблон:Математик, известный своей работой, которая посвящена десятой проблеме Гильберта[1][2].

Биография

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

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

Взнос

Дэвис — один из изобретателей Шаблон:Нп5 и алгоритма DPLL. Также он известен благодаря своей модели машины Поста.

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

В 30-х годах XX века формализуется понятие алгоритм, а также появляются первые примеры алгоритмически неразрешимых теорий в математической логике. Важным моментом стало доказательство Андреем Марковым и Эмилем Постом (независимо друг от друга) неразрешимости Шаблон:Нп5[3] в 1947 году. Это было первое доказательство неразрешимости алгебраической задачи. Трудности, с которыми столкнулись исследователи диофантовых уравнений, вызвали предположение, что необходимого Гильбертом алгоритма не существует. Немного ранее, в 1944 году, Эмиль Пост в одной из своих работ уже писал, что десятая проблема «молит о доказательстве неразрешимости» (Шаблон:Lang-en).

Гипотеза Дэвиса

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

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

<math>P (a_1, \ldots, a_n, x_1, \ldots, x_m) = 0,</math>

где многочлен <math>P</math> с целыми коэффициентами можно разделить на две части — параметры <math>a_1, \ldots, a_n</math> и переменные <math>x_1, \ldots, x_m.</math> При одном наборе значений параметров уравнения может иметь решение, при другом решений может его не иметь. Дэвис выделил множество <math>M</math>, которое содержит все наборы значений параметров (<math>n</math>), при которых уравнение имеет решение:

<math>\{ a_1, \ldots, a_n \} \in M \Longleftrightarrow \exists x_1, \ldots, x_m \colon P(a_1, \ldots, a_n, x_1, \ldots, x_m) = 0.</math>

Такую запись он назвал диофантовым представлением множества, а само множество также назвал диофантовым. Для доказательства неразрешимости десятой проблемы нужно было лишь показать диофантовость любого перечислимое множества, то есть показать возможность построения уравнения, которое имело бы натуральные корни <math>x_1, \ldots, x_m</math> при <math>\{a_1, \ldots, a_n\}</math>, принадлежащих к этому множеству: поскольку среди перечислимых множеств содержатся неразрешимые, то, взяв неразрешимое множество <math>M</math> за основу, невозможно было бы получить общий метод, который бы <math>n</math> определял, имеются ли в этом наборе уравнения натуральные корни. Всё это привело Дэвиса к такой гипотезе: Шаблон:Теорема Дэвис также сделал первый шаг — доказал, что любое перечислимое множество <math>M</math> можно представить в виде:

<math>\{ a_1, \ldots, a_n \} \in M \Longleftrightarrow \exists z \forall y<z \exists x_1, \ldots, x_m \colon P(a_1, \ldots, a_n, x_1, \ldots, x_m, y, z) = 0.</math>

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

Награды и почётные звания

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

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

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

Отдельные издания

Книги
Обзор «двигателей логики»: Шаблон:CitationШаблон:Недоступная ссылка
Статьи
  • Мартин Дэвис (1995), «Является ли математическое понимание алгоритмическим», «Behavioral and Brain Sciences», 13(4), 659-60.

См. также

Примечания

Шаблон:Примечания

Ссылки

Шаблон:Вс

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ 1,0 1,1 Шаблон:Citation Шаблон:Wayback.
  2. ↑ 2,0 2,1 2,2 2,3 Шаблон:MacTutor Biography
  3. ↑ Шаблон:Cite web
  4. ↑ List of Fellows of the American Mathematical Society Шаблон:Архивировано, retrieved 2014-03-17.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Дэвис,_Мартин_(математик)&oldid=9816386