Мартин Дэвид Дэвис (, 8 марта 1928 — 1 января 2023) — американский , известный своей работой, которая посвящена десятой проблеме Гильберта ..
Биография Родители Дэвиса иммигрировали в США из города Лодзь (Польша). Встретившись уже в Нью-Йорке, они поженились. Дэвис родился и вырос в городе Бронкс. Родители с детства поощряли Мартина получить высшее образование.
В 1950 году под руководством Алонзо Черча Мартин получил степень доктора в Принстонском университете, который является одним из старейших и самых престижных университетов США.
Взнос Дэвис — один из изобретателей и алгоритма DPLL. Также он известен благодаря своей модели машины Поста.
Десятая проблема Гильберта В 30-х годах XX века формализуется понятие алгоритм, а также появляются первые примеры алгоритмически неразрешимых теорий в математической логике. Важным моментом стало доказательство Андреем Марковым и Эмилем Постом (независимо друг от друга) неразрешимости в 1947 году. Это было первое доказательство неразрешимости алгебраической задачи. Трудности, с которыми столкнулись исследователи диофантовых уравнений, вызвали предположение, что необходимого Гильбертом алгоритма не существует. Немного ранее, в 1944 году, Эмиль Пост в одной из своих работ уже писал, что десятая проблема «молит о доказательстве неразрешимости» ().
Гипотеза Дэвиса Слова Поста вдохновили студента Мартина Дэвиса на поиск доказательств неразрешимости десятой проблемы. Дэвис перешёл от её формулировки в целых числах к более естественной для теории алгоритмов формулировки в натуральных числах. Это две разные задачи, однако каждая из них сводится к другой. В 1953 году он опубликовал работу, в которой наметил путь решения десятой проблемы в натуральных числах.
Дэвис наравне с классическими диофантовыми уравнениями рассмотрел их параметрическую версию:
где многочлен с целыми коэффициентами можно разделить на две части — параметры и переменные При одном наборе значений параметров уравнения может иметь решение, при другом решений может его не иметь. Дэвис выделил множество , которое содержит все наборы значений параметров (), при которых уравнение имеет решение:
Такую запись он назвал диофантовым представлением множества, а само множество также назвал диофантовым. Для доказательства неразрешимости десятой проблемы нужно было лишь показать диофантовость любого перечислимое множества, то есть показать возможность построения уравнения, которое имело бы натуральные корни при , принадлежащих к этому множеству: поскольку среди перечислимых множеств содержатся неразрешимые, то, взяв неразрешимое множество за основу, невозможно было бы получить общий метод, который бы определял, имеются ли в этом наборе уравнения натуральные корни. Всё это привело Дэвиса к такой гипотезе:
Дэвис также сделал первый шаг — доказал, что любое перечислимое множество можно представить в виде:
Это получило название «нормальная форма Дэвиса». Доказать свою гипотезу, избавившись от квантора всеобщности, ему на тот момент не удалось.
Награды и почётные звания В 1975 году, Дэвис был награждён премией Стила, премией «Chauvenet Prize» и премией Лестера Форда за работу, которая посвящена десятой проблеме Гильберта.
В 1982 году Мартин стал членом и Американской академии искусств и наук.
В 2012 был избран стипендиатом Американского математического обществаList of Fellows of the American Mathematical Society , retrieved 2014-03-17..
Отдельные издания Книги
Обзор «двигателей логики»:
Статьи Мартин Дэвис (1995), «Является ли математическое понимание алгоритмическим», «Behavioral and Brain Sciences», 13(4), 659-60.
См. также Проблема остановки Нестандартный анализ
Примечания
Ссылки Сайт Мартина Дэвиса
Категория:Математики в теории чисел Категория:Логики США Категория:Члены Американской академии искусств и наук Категория:Действительные члены Американского математического общества Категория:Выпускники Средней школы естественных наук Бронкса Категория:Выпускники Принстонского университета Категория:Лауреаты премии Шовене Категория:Преподаватели Нью-Йоркского университета Категория:Преподаватели Курантовского института математических наук