Мартін Девіс

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Мартін Девіс
Martin Davis
Мартін Девіс
Мартін Девіс
Народився 1928(1928)
Нью-Йорк
Країна Flag of the United States.svg США
Національність Американець
Діяльність математик, викладач університету, інформатик
Alma mater Принстонський університет
Галузь теорія чисел
Заклад Нью-Йоркський університет
Науковий керівник Алонзо Черч
Аспіранти, докторанти Moshe Koppeld, Donald W. Lovelandd[1], Donald Perlisd[1], Robert Arnold Di Paolad[1], Edward Norman Schwartzd[1], John Denesd[1], Richard Gostaniand[1], Keith Harrowd[1], Barry Jacobsd[1], Richard Marshall Rosenbergd[1], Jean-Pierre Kellerd[1], David Linfieldd[1], Ronald Fechterd[1], Thomas Emersond[1], Martin Michael Zuckermand[1], Eric G. Wagnerd[1], Alberto Policritid[1], Ron Mark Sigald[1] і Eugenio Giovanni Omodeod[1]
Членство Американське математичне товариство і Американська академія мистецтв і наук
Відомий завдяки: Алгоритм Девіса-Патнема[en]
Алгоритм DPLL
робота над десятою проблемою Гільберта
Нагороди Премія Шовене[en] (1975)

CMNS: Мартін Девіс у Вікісховищі

Мартін Девід Девіс (англ. Martin Davis, народився у 1928 році) — американський математик, відомий своєю роботою, яка присвячена десятій проблемі Гільберта.[2][3]

Біографія[ред. | ред. код]

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

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

Внесок[ред. | ред. код]

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

Десята проблема Гільберта[ред. | ред. код]

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

Гіпотеза Девіса[ред. | ред. код]

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

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

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

Такий запис він назвав діофантовим представленням множини, а саму множину також назвав діофантова. Для доказу нерозв'язності десятої проблеми потрібно було лише показати діофантовість будь-якогї зліченної множини, тобто показати можливість побудови рівняння, яке мало б натуральні корені лише при всіх , що належать цій зліченній множині: оскільки серед перелічуваних множин містяться нерозв'язні, то, взявши нерозв'язну множину за основу, неможливо було б отримати загальний метод, який би визначав, чи має на цьому наборі рівняння натуральні корені. Все це привело Девіса до такої гіпотези:

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

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

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

Нагороди та почесні звання[ред. | ред. код]

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

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

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

Окремі видання[ред. | ред. код]

Книги
  • Мартін, Девіс (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.

Див. також[ред. | ред. код]

Посилання[ред. | ред. код]

Примітки[ред. | ред. код]