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

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

Биография

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

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

Взнос

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Книги
  • Мартин, Дэвис. Прикладной нестандартный анализ (неопр.) . — Нью-Йорк: Wiley, 1977. — ISBN 9780471198970 .
  • Мартин, Дэвис; Джессика, Элейн; Рон, Сигал. Вычислимости, сложность и речи: Основы теоретической информатики . — 2-й том. — Бостон: Academic Press, Harcourt, Brace, 1994. — ISBN 9780122063824 .
  • Мартин, Дэвис. Двигатели логики: математика и происхождение компьютера . — Нью-Йорк: Norton, 2000. — ISBN 9780393322293 .
Обзор «двигателей логики»: Уоллес, Ричард, , ALICE A. I. Foundation. {{ citation }} : Недопустимый |ref=harv ( справка ) (недоступная ссылка)
Статьи
  • Мартин Дэвис (1995), «Является ли математическое понимание алгоритмическим», «Behavioral and Brain Sciences», 13(4), 659-60.

См. также

Примечания

  1. Jackson, Allyn (September 2007), (PDF) , Notices of the American Mathematical Society , Providence, RI : American Mathematical Society (published 2008), vol. 55, no. 5, pp. 560—571, ISSN , OCLC {{ citation }} : Проверьте значение даты: |year= / |date= mismatch ( справка ) . Дата обращения: 5 сентября 2017. Архивировано 19 июля 2020 года. .
  2. Джон Дж. О’Коннор и Эдмунд Ф. Робертсон . (англ.) — биография в архиве MacTutor .
  3. . Дата обращения: 31 марта 2022. 22 декабря 2016 года.
  4. от 16 мая 2019 на Wayback Machine , retrieved 2014-03-17.

Ссылки

Источник —

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