Мартін Девіс
Мартін Девід Девіс (англ. 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 році він опублікував роботу, в якій намітив шлях вирішення десятої проблеми в натуральних числах.
Девіс нарівні з класичними діофантовими рівняннями розглянув їхню параметричну версію:
де многочлен з цілими коефіцієнтами можна розділити на дві частини — параметри та змінні При одному наборі значень параметрів рівняння може мати рішення, при іншому рішень може не існувати. Девіс виділив множину , яка містить всі набори значень параметрів (), при яких рівняння має рішення:
Такий запис він назвав діофантовим представленням множини, а саму множину також назвав діофантова. Для доказу нерозв'язності десятої проблеми потрібно було лише показати діофантовість будь-якогї зліченної множини, тобто показати можливість побудови рівняння, яке мало б натуральні корені лише при всіх , що належать цій зліченній множині: оскільки серед перелічуваних множин містяться нерозв'язні, то, взявши нерозв'язну множину за основу, неможливо було б отримати загальний метод, який би визначав, чи має на цьому наборі рівняння натуральні корені. Все це привело Девіса до такої гіпотези:
|
Девіс також зробив перший крок — довів, що будь-яку зліченну множину можна представити у вигляді:
Це дістало назву «нормальна форма Девіса». Довести свою гіпотезу, позбувшись квантора загальності, йому на той момент не вдалося.
Нагороди та почесні звання[ред. | ред. код]
В 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.]
Примітки[ред. | ред. код]
- ↑ а б в г д е ж и к л м н п Архів історії математики Мактьютор — 1994.
- ↑ Martin David Davis
- ↑ https://www.legacy.com/us/obituaries/name/martin-davis-obituary?id=38544823
- ↑ Czech National Authority Database
- ↑ https://www.ias.edu/scholars/martin-d-davis
- ↑ а б в г д е ж и к л м н п р с т у ф х Математичний генеалогічний проєкт — 1997.
- ↑ http://www.ams.org/fellows_by_year.cgi?year=2013
- ↑ http://www.ams.org/news?news_id=1680
- ↑ а б 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.
- ↑ а б в г Джон Дж. О'Коннор та Едмунд Ф. Робертсон. Мартін Девіс в архіві MacTutor (англ.)
- ↑ Архівована копія. Архів оригіналу за 22 грудня 2016. Процитовано 17 березня 2022.
{{cite web}}
: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання) - ↑ Архівована копія. Архів оригіналу за 1 жовтня 2014. Процитовано 30 жовтня 2014.
{{cite web}}
: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання) - ↑ List of Fellows of the American Mathematical Society [Архівовано 2018-08-25 у Wayback Machine.], retrieved 2014-03-17.
|
- Народились 8 березня
- Народились 1928
- Уродженці Нью-Йорка
- Померли 1 січня
- Померли 2023
- Померли в Берклі
- Випускники Принстонського університету
- Випускники Сіті-коледжу
- Викладачі Нью-Йоркського університету
- Науковці Університету Іллінойсу в Урбана-Шампейн
- Викладачі Університету штату Огайо
- Члени Американської академії мистецтв і наук
- Члени Американського математичного товариства
- Логіки