Просмотр кода страницы Дэвис, Мартин (математик)

{{ФИО}}
{{Учёный
|Оригинал имени = {{lang-en|Martin Davis}}
}}

'''Мартин Дэвид Дэвис''' ({{lang-en|Martin Davis}}, [[8 марта]] [[1928 год|1928]] — [[1 января]] [[2023 год|2023]]) — [[Соединённые Штаты Америки|американский]] {{математик|США}}, известный своей работой, которая посвящена [[Десятая проблема Гильберта|десятой проблеме Гильберта]]<ref name="jackson">{{Citation
|last = Jackson
|first = Allyn
|publication-date = 2008
|date = September 2007
|year = 2008
|url = http://www.ams.org/notices/200805/tx080500560p.pdf
|title = Interview with Martin Davis
|periodical = [[Notices of the American Mathematical Society]]
|publication-place = [[Провиденс|Providence, RI]]
|publisher = [[Американское математическое общество|American Mathematical Society]]
|volume = 55
|issue = 5
|pages = 560—571
|issn = 0002-9920
|oclc = 1480366
|access-date = 2017-09-05
|archive-date = 2020-07-19
|archive-url = https://web.archive.org/web/20200719024910/http://www.ams.org/notices/200805/tx080500560p.pdf
|url-status = live
}} {{Cite web |url=http://www.ams.org/notices/200805/tx080500560p.pdf |title=Источник |access-date=2017-09-05 |archive-date=2020-07-19 |archive-url=https://web.archive.org/web/20200719024910/http://www.ams.org/notices/200805/tx080500560p.pdf |deadlink=unfit }}.</ref><ref name="mactutor">{{MacTutor Biography|id=Davis|title=Мартин Дэвис}}</ref>.

== Биография ==
Родители Дэвиса иммигрировали в [[США]] из города [[Лодзь]] ([[Польша]]). Встретившись уже в [[Нью-Йорк]]е, они поженились. Дэвис родился и вырос в городе [[Бронкс]]. Родители с детства поощряли Мартина получить высшее образование<ref name="jackson"/><ref name="mactutor"/>.

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

== Взнос ==
Дэвис — один из изобретателей {{нп5|Алгоритм Дэвиса-Путнама|алгоритма Дэвиса-Путнама||Davis–Putnam algorithm}} и [[Алгоритм DPLL|алгоритма DPLL]]. Также он известен благодаря своей модели [[Машина Поста|машины Поста]].

== Десятая проблема Гильберта ==
В [[1930-е|30-х]] годах XX века формализуется понятие [[алгоритм]], а также появляются первые примеры алгоритмически неразрешимых [[множество|теорий]] в [[Математическая логика|математической логике]]. Важным моментом стало доказательство [[Марков, Андрей Андреевич (младший)|Андреем Марковым]] и [[Эмиль Пост|Эмилем Постом]] (независимо друг от друга) неразрешимости {{Нп5|Задача Туе|задачи Туе||Semi-Thue system#The word problem for semi-Thue systems}}<ref>{{Cite web |url=http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%BD%D0%B5%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%3A_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%B2%D1%8B%D0%B2%D0%BE%D0%B4%D0%B5_%D0%B2_%D0%BF%D0%BE%D0%BB%D1%83%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B5_%D0%A2%D1%83%D1%8D |title=Примеры неразрешимых задач: задача о выводе в полусистеме Туэ |access-date=2022-03-31 |archive-date=2016-12-22 |archive-url=https://web.archive.org/web/20161222041101/http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%BD%D0%B5%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87:_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%B2%D1%8B%D0%B2%D0%BE%D0%B4%D0%B5_%D0%B2_%D0%BF%D0%BE%D0%BB%D1%83%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B5_%D0%A2%D1%83%D1%8D |deadlink=no }}</ref> в 1947 году. Это было первое доказательство неразрешимости [[алгебра]]ической задачи. Трудности, с которыми столкнулись исследователи [[Диофантовы уравнения|диофантовых уравнений]], вызвали предположение, что необходимого [[Гильберт, Давид|Гильбертом]] [[алгоритм]]а не существует. Немного ранее, в 1944 году, [[Эмиль Пост]] в одной из своих работ уже писал, что десятая проблема «молит о доказательстве неразрешимости» ({{lang-en|«Begs for an unsolvability proof»}}).

=== Гипотеза Дэвиса ===
Слова [[Пост, Эмиль|Поста]] вдохновили студента Мартина Дэвиса на поиск доказательств неразрешимости десятой проблемы. Дэвис перешёл от её формулировки в [[Целые числа|целых числах]] к более естественной для [[Теория алгоритмов|теории алгоритмов]] формулировки в [[Натуральные числа|натуральных числах]]. Это две разные задачи, однако каждая из них сводится к другой. В 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» и премией Лестера Форда за работу, которая посвящена [[Десятая проблема Гильберта|десятой проблеме Гильберта]]<ref name="mactutor"/>.

В 1982 году Мартин стал членом [[Американская академия искусств и наук|и Американской академии искусств и наук]]<ref name="mactutor"/>.

В 2012 был избран стипендиатом [[Американское математическое общество|Американского математического общества]]<ref>[http://www.ams.org/profession/fellows-list List of Fellows of the American Mathematical Society] {{Wayback|url=http://www.ams.org/profession/fellows-list |date=20190516093104 }}, retrieved 2014-03-17.</ref>.

== Отдельные издания ==
'''Книги'''
* {{книга |заглавие=Прикладной нестандартный анализ |ссылка=https://archive.org/details/appliednonstanda0000davi |издательство=Wiley |место=Нью-Йорк |год=1977 |isbn=9780471198970 |язык=und |автор=Мартин, Дэвис}}
* {{книга |заглавие=Вычислимости, сложность и речи: Основы теоретической информатики |издательство=Academic Press, Harcourt, Brace |место=Бостон |год=1994 |издание=2-й том |isbn=9780122063824 |язык=ru |автор=Мартин, Дэвис; Джессика, Элейн; Рон, Сигал}}
* {{книга |заглавие=Двигатели логики: математика и происхождение компьютера |издательство=Norton |место=Нью-Йорк |год=2000 |isbn=9780393322293 |язык=ru |автор=Мартин, Дэвис}}
:: Обзор «двигателей логики»: {{citation| first =Ричард| last =Уоллес| title =Математики которые забывают ошибки истории: обзор двигателей логики("Мартин Дэвис")| url =http://www.alicebot.org/articles/wallace/mathematicia..| publisher =ALICE A. I. Foundation| postscript =.}}{{Недоступная ссылка|date=2018-06|bot=InternetArchiveBot }}

'''Статьи'''
* Мартин Дэвис (1995), «Является ли математическое понимание алгоритмическим», «Behavioral and Brain Sciences», 13(4), 659-60.

== См. также ==
* [[Проблема остановки]]
* [[Нестандартный анализ]]

== Примечания ==
{{примечания}}

== Ссылки ==
* [http://www.cs.nyu.edu/cs/faculty/davism/ Сайт Мартина Дэвиса] {{Wayback|url=http://www.cs.nyu.edu/cs/faculty/davism/ |date=20140928090903 }}
* {{Math-Net.ru|37250|}}

{{вс}}

[[Категория:Математики в теории чисел]]
[[Категория:Логики США]]
[[Категория:Члены Американской академии искусств и наук]]
[[Категория:Действительные члены Американского математического общества]]
[[Категория:Выпускники Принстонского университета]]
[[Категория:Лауреаты премии Шовене]]
[[Категория:Преподаватели Нью-Йоркского университета]]
[[Категория:Преподаватели Курантовского института математических наук]]