Показать меню

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

25.03.2022
31

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

Биография

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

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

Взнос

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

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

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

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

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

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

P ( a 1 , … , a n , x 1 , … , x m ) = 0 , {displaystyle P(a_{1},ldots ,a_{n},x_{1},ldots ,x_{m})=0,}

где многочлен P {displaystyle P} с целыми коэффициентами можно разделить на две части — параметры a 1 , … , a n {displaystyle a_{1},ldots ,a_{n}} и переменные x 1 , … , x m . {displaystyle x_{1},ldots ,x_{m}.} При одном наборе значений параметров уравнения может иметь решение, при другом решений может его не иметь. Дэвис выделил множество M {displaystyle M} , которое содержит все наборы значений параметров ( n {displaystyle n} ), при которых уравнение имеет решение:

{ a 1 , … , a n } ∈ M ⟺ ∃ x 1 , … , x m : P ( a 1 , … , a n , x 1 , … , x m ) = 0. {displaystyle {a_{1},ldots ,a_{n}}in MLongleftrightarrow exists x_{1},ldots ,x_{m}colon P(a_{1},ldots ,a_{n},x_{1},ldots ,x_{m})=0.}

Такую запись он назвал диофантовым представлением множества, а само множество также назвал диофантовым. Для доказательства неразрешимости десятой проблемы нужно было лишь показать диофантовость любого перечислимое множества, то есть показать возможность построения уравнения, которое имело бы натуральные корни x 1 , … , x m {displaystyle x_{1},ldots ,x_{m}} при { a 1 , … , a n } {displaystyle {a_{1},ldots ,a_{n}}} , принадлежащих к этому множеству: поскольку среди перечислимых множеств содержатся неразрешимые, то, взяв неразрешимое множество M {displaystyle M} за основу, невозможно было бы получить общий метод, который бы n {displaystyle n} определял, имеются ли в этом наборе уравнения натуральные корни. Все это привело Дэвиса к такой гипотезе:

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

{ a 1 , … , a n } ∈ M ⟺ ∃ z ∀ y < z ∃ x 1 , … , x m : P ( a 1 , … , a n , x 1 , … , x m , y , z ) = 0. {displaystyle {a_{1},ldots ,a_{n}}in MLongleftrightarrow exists zforall y<zexists x_{1},ldots ,x_{m}colon P(a_{1},ldots ,a_{n},x_{1},ldots ,x_{m},y,z)=0.}

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

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

В 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, <http://www.alicebot.org/articles/wallace/mathematicia..> (недоступная ссылка) Статьи
  • Мартин Дэвис (1995), «Является ли математическое понимание алгоритмическим», «Behavioral and Brain Sciences», 13(4), 659-60.
Еще по этой теме:
Дэвис, Клайв
21:00, 16 октябрь
Дэвис, Клайв
Клайв Дэвис (англ. Clive Davis, род. 4 апреля 1932) — американский музыкальный продюсер, видный деятель музыкальной индустрии. Президент лейбла Columbia Records в 1967—1973 годах и основатель Arista
Якоби, Мартин
04:29, 14 декабрь
Якоби, Мартин
Мартин Якоби (нем. Martin Jacobi, англ. Martin Jacoby, 12 апреля 1842, Гамбург — 24 декабря 1907, Лондон) — немецкий музыкант и энтомолог. Биография Мартин Якоби родился 12 апреля 1842 года в районе
Коддингтон, Эдвин Фостер
21:59, 13 декабрь
Коддингтон, Эдвин Фостер
Эдвин Фостер Коддингтон (англ. Edwin Foster Coddington 24 июня 1870 — 21 декабря 1950) — американский астроном и математик. Наиболее известен как первооткрыватель кометы Коддингтона-Паули, астероидов
Дэвис, Говард
22:37, 12 декабрь
Дэвис, Говард
Говард Эдвард Дэвис младший (англ. Howard Edward Davis, Jr.; 14 февраля 1956, Глен-Ков — 30 декабря 2015, Плантейшен, Флорида, США) — американский боксёр лёгких весовых категорий, выступал за сборную
Грейтцер, Самуэль
06:11, 07 декабрь
Грейтцер, Самуэль
Сэмюэль Грейтцер (10 августа 1905 — 22 февраля 1988) — американский математик и педагог. Наиболее известен как основатель и председатель математической Олимпиады в США. Биография Родился в России,
Мартин, Ли Эндрю
06:10, 05 декабрь
Мартин, Ли Эндрю
Ли Эндрю Мартин (англ. Lee Andrew Martin; родился 5 февраля 1968 года в Хайде, Большой Манчестер) — английский футболист, левый защитник. Наиболее известен по выступлениям за клубы «Манчестер
Комментарии:
Добавить комментарий
Ваше Имя:
Ваш E-Mail: