Мартін Девіс

Шаблон:Науковець Шаблон:Othernames Мартін Девід Девіс (Шаблон:Lang-en; 8 березня 1928 — 1 січня 2023) — американський математик, відомий своєю роботою, яка присвячена десятій проблемі Гільберта.

Біографія

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

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

Внесок

Девіс — один з винахідників Шаблон:Не перекладено та алгоритму DPLL. Також він відомий завдяки своїй моделі машини Поста.

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

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

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

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

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

$P(a_1,\dots ,a_n,x_1,\dots ,x_m)=0,$

де многочлен $P$ з цілими коефіцієнтами можна розділити на дві частини — параметри $a_1,\dots ,a_n$ та змінні $x_1,\dots ,x_m.$ При одному наборі значень параметрів рівняння може мати рішення, при іншому рішень може не існувати. Девіс виділив множину $M$, яка містить всі набори значень параметрів ($n$), при яких рівняння має рішення:

$𝒽a_1,\dots ,a_n𝒾\in M⟺\mathrm{\exists }{x}_1,\dots ,x_m𝒻P(a_1,\dots ,a_n,x_1,\dots ,x_m)=0ℊ.$

Такий запис він назвав діофантовим представленням множини, а саму множину також назвав діофантова. Для доказу нерозв'язності десятої проблеми потрібно було лише показати діофантовість будь-якої зліченної множини, тобто показати можливість побудови рівняння, яке мало б натуральні корені $x_1,\dots ,x_m$ лише при всіх $𝒽a_1,\dots ,a_n𝒾$, що належать цій зліченній множині: оскільки серед перелічуваних множин містяться нерозв'язні, то, взявши нерозв'язну множину $M$ за основу, неможливо було б отримати загальний метод, який би $n$ визначав, чи має на цьому наборі рівняння натуральні корені. Все це привело Девіса до такої гіпотези: Шаблон:Теорема Девіс також зробив перший крок — довів, що будь-яку зліченну множину $M$ можна представити у вигляді:

$𝒽a_1,\dots ,a_n𝒾\in M⟺\mathrm{\exists }z\mathrm{\forall }y<z\mathrm{\exists }{x}_1,\dots ,x_m𝒻P(a_1,\dots ,a_n,x_1,\dots ,x_m,y,z)=0ℊ.$

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

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

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

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

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

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

Книги

• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book

Огляд двигунів логіки: Шаблон:CitationШаблон:Недоступне посилання

Статті

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

Див. також

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

Посилання

• Сторінка Мартіна Девіса Шаблон:Webarchive