Мартін Девіс

|Батько= |Посада= |Діти= |Мати= |Дружина= |Чоловік=

Мартін Девіс
Martin Davis
Мартін Девіс Мартін Девіс
Ім'я при народженні	англ. Martin David Davis[1]
Народився	8 березня 1928(1928-03-08)  Нью-Йорк, США
Помер	1 січня 2023(2023-01-01)[2] (94 роки)  Берклі, Каліфорнія, США
Поховання	Cypress Lawn Memorial Park^d[3]
Країна	США
Національність	Американець
Діяльність	математик, викладач університету, інформатик
Alma mater	Принстонський університет (1950)[1] Вища наукова школа Бронксу^d (1944)[1] Сіті Коледж (1948)[1]
Галузь	теорія чисел, математика[4], Hilbert's tenth problem^d[1] і теорія обчислюваності
Заклад	Нью-Йоркський університет[1] Університет Іллінойсу в Урбана-Шампейн[1] Інститут перспективних досліджень[1][5] Університет Каліфорнії в Дейвісі[1] Університет штату Огайо[1] Політехнічний інститут Ренсселера[1] Університет Єшива^d[1] Нью-Йоркський університет[1]
Науковий керівник	Алонзо Черч
Аспіранти, докторанти	Moshe Koppel^d[6] Donald W. Loveland^d[6] Donald Perlis^d[6] Robert Arnold Di Paola^d[6] Edward Norman Schwartz^d[6] John Denes^d[6] Richard Gostanian^d[6] Keith Harrow^d[6] Barry Jacobs^d[6] Richard Marshall Rosenberg^d[6] Jean-Pierre Keller^d[6] David Linfield^d[6] Ronald Fechter^d[6] Thomas Emerson^d[6] Martin Michael Zuckerman^d[6] Eric G. Wagner^d[6] Alberto Policriti^d[6] Ron Mark Sigal^d[6] Eugenio Giovanni Omodeo^d[6]
Членство	Американська академія мистецтв і наук Американське математичне товариство[7][8]
Відомий завдяки:	Алгоритм Девіса-Патнема^[en] Алгоритм DPLL робота над десятою проблемою Гільберта
Нагороди	Премія Шовене^[en] (1975)
Особ. сторінка	cs.nyu.edu/cs/faculty/davism/
Мартін Девіс у Вікісховищі

Мартін Девід Девіс (англ. Martin Davis; 8 березня 1928 — 1 січня 2023) — американський математик, відомий своєю роботою, яка присвячена десятій проблемі Гільберта.[9][10]

Біографія

Батьки Девіса іммігрували до США з міста Лодзь (Польща). Зустрівшись вже в Нью-Йорку, вони одружились. Девіс народився та виріс в місті Бронкс. Батьки з дитинства заохочували Мартіна здобути вищу освіту .[9][10]

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

Внесок

Девіс — один з винахідників алгоритму Девіса-Путнама^[en] та алгоритму DPLL. Також він відомий завдяки своїй моделі машини Поста.

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

В 30-х роках ХХ ст. формалізується поняття алгоритму, а також з'являються перші приклади алгоритмічно нерозв'язних множин в математичній логіці. Важливим моментом став доказ Андрієм Марковим і Емілем Постом (незалежно один від одного) нерозв'язності задачі Туе^[en][11][12] в 1947 році. Це був перший доказ нерозв'язності алгебраїчної задачі. Він, а також труднощі, з якими зіткнулися дослідники діофантових рівнянь, викликали припущення, що необхідного Гільбертом алгоритму не існує. Трохи раніше, в 1944 році, Еміль Пост в одній зі своїх робіт вже писав, що десята проблема «молить про доказ нерозв'язності» (англ. «Begs for an unsolvability proof»).

Гіпотеза Девіса

Слова Поста надихнули студента Мартіна Девіса на пошук доказів нерозв'язності десятої проблеми. Девіс перейшов від її формулювання в цілих числах до більш природного для теорії алгоритмів формулювання в натуральних числах. Це дві різні задачі, проте кожна з них зводиться до іншої. У 1953 році він опублікував роботу, в якій намітив шлях вирішення десятої проблеми в натуральних числах.

Девіс нарівні з класичними діофантовими рівняннями розглянув їхню параметричну версію:

${\displaystyle P(a_{1},\ldots ,a_{n},x_{1},\ldots ,x_{m})=0,}$

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

${\displaystyle {\mathcal {h}}a_{1},\ldots ,a_{n}{\mathcal {i}}\in M\Longleftrightarrow \exists x_{1},\ldots ,x_{m}{\mathcal {f}}P(a_{1},\ldots ,a_{n},x_{1},\ldots ,x_{m})=0{\mathcal {g}}.}$

Такий запис він назвав діофантовим представленням множини, а саму множину також назвав діофантова. Для доказу нерозв'язності десятої проблеми потрібно було лише показати діофантовість будь-якогї зліченної множини, тобто показати можливість побудови рівняння, яке мало б натуральні корені ${\displaystyle x_{1},\ldots ,x_{m}}$ лише при всіх ${\displaystyle {\mathcal {h}}a_{1},\ldots ,a_{n}{\mathcal {i}}}$, що належать цій зліченній множині: оскільки серед перелічуваних множин містяться нерозв'язні, то, взявши нерозв'язну множину ${\displaystyle M}$ за основу, неможливо було б отримати загальний метод, який би ${\displaystyle n}$ визначав, чи має на цьому наборі рівняння натуральні корені. Все це привело Девіса до такої гіпотези:

Поняття діофантової та зліченної множини збігаються. Це значить, що множина діофантова тоді і лише тоді, коли вона зліченна.

Девіс також зробив перший крок — довів, що будь-яку зліченну множину ${\displaystyle M}$ можна представити у вигляді:

${\displaystyle {\mathcal {h}}a_{1},\ldots ,a_{n}{\mathcal {i}}\in M\Longleftrightarrow \exists z\forall y<z\exists x_{1},\ldots ,x_{m}{\mathcal {f}}P(a_{1},\ldots ,a_{n},x_{1},\ldots ,x_{m},y,z)=0{\mathcal {g}}.}$

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

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

В 1975 році, Девіс був нагороджений Премією Стіла, премією Chauvenet Prize та премією Lester R. Ford за роботу, яка присвячена десятій проблемі Гільберта.[10]

У 1982 році Мартін став членом Американської академії мистецтв і наук[10].

У 2012 був обраний стипендіатом Американського математичного товариства.[13]

Окремі видання

Книги

• Мартін, Девіс (1977). Прикладний нестандартний аналіз. Нью-Йорк: Wiley. ISBN 9780471198970.
• Мартін, Девіс; Джессіка, Елейн; Рон, Сигал (1994). Обчислюваності, складність і мови: Основи теоретичної інформатики (вид. 2-й том). Бостон: Academic Press, Harcourt, Brace. ISBN 9780122063824.
• Мартін, Девіс (2000). Двигуни логіки: математика та походження комп'ютера. Нью-Йорк: Norton. ISBN 9780393322293.

Огляд двигунів логіки: Уоллес, Ричард, Математики які забувають помилки історії: огляд двигунів логіки(Мартін Девіс), ALICE A.I. Foundation.^[недоступне посилання з квітня 2019]

Статті

• Мартін Девіс (1995), «Чи є математична інтуїція алгоритмічною», Поведінкові та мозкові науки, 13(4), 659-60.

Див. також

• Проблема зупинки

Посилання

• Сторінка Мартіна Девіса [Архівовано 28 вересня 2014 у Wayback Machine.]

Примітки

1. Архів історії математики Мактьютор — 1994.
   d:Track:Q547473
2. Martin David Davis
3. https://www.legacy.com/us/obituaries/name/martin-davis-obituary?id=38544823
4. Чеська національна авторитетна база даних
   d:Track:Q13550863
5. https://www.ias.edu/scholars/martin-d-davis
6. Математичний генеалогічний проєкт — 1997.
   d:Track:Q829984
7. http://www.ams.org/fellows_by_year.cgi?year=2013
8. http://www.ams.org/news?news_id=1680
9. Jackson, Allyn (September 2007), Interview with Martin Davis (PDF), Notices of the American Mathematical Society, Providence, RI: American Mathematical Society, т. 55, № 5, с. 560—571, ISSN 0002-9920, OCLC 1480366, архів оригіналу (PDF) за 19 липня 2020, процитовано 24 жовтня 2014.
10. Джон Дж. О'Коннор та Едмунд Ф. Робертсон. Мартін Девіс в архіві MacTutor (англ.)
11. Архівована копія. Архів оригіналу за 22 грудня 2016. Процитовано 17 березня 2022.
12. Архівована копія. Архів оригіналу за 1 жовтня 2014. Процитовано 30 жовтня 2014.
13. List of Fellows of the American Mathematical Society [Архівовано 2018-08-25 у Wayback Machine.], retrieved 2014-03-17.