Дэвис, Мартин (математик)
Мартин Дэвис | |
---|---|
Martin Davis | |
Дата рождения | 8 марта 1928 |
Место рождения | Нью-Йорк, США |
Дата смерти | 1 января 2023 (94 года) |
Место смерти | Беркли, Калифорния, США |
Страна | США |
Научная сфера | теория чисел и математика |
Альма-матер | Принстонский университет (1950) |
Научный руководитель | Алонзо Чёрч |
Награды и премии |
Herbrand Award (2005), премия Стила (1975), Премия Халмоша — Форда, стипендия Гуггенхайма (1983), действительный член Американского математического общества (2013) |
Сайт | cs.nyu.edu/cs/faculty/da… |
Мартин Дэвид Дэвис (англ. Martin Davis, 8 марта 1928 — 1 января 2023) — американский математик, известный своей работой, которая посвящена десятой проблеме Гильберта[1][2].
Биография
Родители Дэвиса иммигрировали в США из города Лодзь (Польша). Встретившись уже в Нью-Йорке, они поженились. Дэвис родился и вырос в городе Бронкс. Родители с детства поощряли Мартина получить высшее образование[1][2].
В 1950 году под руководством Алонзо Черча Мартин получил степень доктора в Принстонском университете, который является одним из старейших и самых престижных университетов США.
Умер 1 января 2023 года в Беркли.
Вклад в математику
Дэвис — один из изобретателей алгоритма Дэвиса-Путнама[англ.] и алгоритма DPLL. Также он известен благодаря своей модели машины Поста.
Десятая проблема Гильберта
В 30-х годах XX века формализуется понятие алгоритм, а также появляются первые примеры алгоритмически неразрешимых теорий в математической логике. Важным моментом стало доказательство Андреем Марковым и Эмилем Постом (независимо друг от друга) неразрешимость задачи Туе[англ.][3] в 1947 году. Это было первое доказательство неразрешимости алгебраической задачи. Трудности, с которыми столкнулись исследователи диофантовых уравнений, вызвали предположение, что необходимого Гильбертом алгоритма не существует. Немного ранее, в 1944 году, Эмиль Пост в одной из своих работ уже писал, что десятая проблема «молит о доказательстве неразрешимости» (англ. «Begs for an unsolvability proof»).
Гипотеза Дэвиса
Слова Поста вдохновили студента Мартина Дэвиса на поиск доказательств неразрешимости десятой проблемы. Дэвис перешел от её формулировки в целых числах к более естественной для теории алгоритмов формулировки в натуральных числах. Это две разные задачи, однако каждая из них сводится к другой. В 1953 году он опубликовал работу, в которой наметил путь решения десятой проблемы в натуральных числах.
Дэвис наравне с классическими диофантовыми уравнениями рассмотрел их параметрическую версию:
- [math]\displaystyle{ P (a_1, \ldots, a_n, x_1, \ldots, x_m) = 0, }[/math]
где многочлен [math]\displaystyle{ P }[/math] с целыми коэффициентами можно разделить на две части — параметры [math]\displaystyle{ a_1, \ldots, a_n }[/math] и переменные [math]\displaystyle{ x_1, \ldots, x_m. }[/math] При одном наборе значений параметров уравнения может иметь решение, при другом решений может его не иметь. Дэвис выделил множество [math]\displaystyle{ M }[/math], которое содержит все наборы значений параметров ([math]\displaystyle{ n }[/math]), при которых уравнение имеет решение:
- [math]\displaystyle{ \{ 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]\displaystyle{ x_1, \ldots, x_m }[/math] при [math]\displaystyle{ \{a_1, \ldots, a_n\} }[/math], принадлежащих к этому множеству: поскольку среди перечислимых множеств содержатся неразрешимые, то, взяв неразрешимое множество [math]\displaystyle{ M }[/math] за основу, невозможно было бы получить общий метод, который бы [math]\displaystyle{ n }[/math] определял, имеются ли в этом наборе уравнения натуральные корни. Все это привело Дэвиса к такой гипотезе:
|
Дэвис также сделал первый шаг — доказал, что любое перечислимое множество [math]\displaystyle{ M }[/math] можно представить в виде:
- [math]\displaystyle{ \{ a_1, \ldots, a_n \} \in M \Longleftrightarrow \exists z \forall y\lt 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].
Отдельные издания
- Книги
- Мартин, Дэвис. Прикладной нестандартный анализ (неопр.). — Нью-Йорк: 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), «Является ли математическое понимание алгоритмическим», «Behavioral and Brain Sciences», 13(4), 659-60.
См. также
Примечания
- ↑ 1,0 1,1 Jackson, Allyn (September 2007), Interview with Martin Davis, Notices of the American Mathematical Society (Providence, RI: American Mathematical Society) . — Т. 55 (5): 560—571, 2008, ISSN 0002-9920, OCLC 1480366, <http://www.ams.org/notices/200805/tx080500560p.pdf> Архивная копия от 19 июля 2020 на Wayback Machine.
- ↑ 2,0 2,1 2,2 2,3 Джон Дж. О’Коннор и Эдмунд Ф. Робертсон. Мартин Дэвис (англ.) — биография в архиве MacTutor.
- ↑ Примеры неразрешимых задач: задача о выводе в полусистеме Туэ . Дата обращения: 31 марта 2022. Архивировано 22 декабря 2016 года.
- ↑ List of Fellows of the American Mathematical Society Архивировано 13 августа 2013 года., retrieved 2014-03-17.
Ссылки
- Сайт Мартина Дэвиса Архивная копия от 28 сентября 2014 на Wayback Machine
- Родившиеся 8 марта
- Родившиеся в 1928 году
- Персоналии по алфавиту
- Родившиеся в Нью-Йорке
- Умершие 1 января
- Умершие в 2023 году
- Умершие в Беркли
- Учёные по алфавиту
- Математики по алфавиту
- Математики США
- Математики в теории чисел
- Логики США
- Члены Американской академии искусств и наук
- Действительные члены Американского математического общества
- Выпускники Принстонского университета
- Лауреаты премии Шовене
- Преподаватели Нью-Йоркского университета
- Преподаватели Курантовского института математических наук
- Преподаватели по алфавиту