Мартин Дэвис¶

Мартин Дэвис (англ. Martin Davis; 8 марта 1928, Нью-Йорк — 1 января 2023, Беркли, Калифорния) — американский математик, известный своими фундаментальными работами в области математической логики, теории алгоритмов и вычислимости. Внёс значительный вклад в решение десятой проблемы Гильберта, разработку алгоритмических методов в логике и популяризацию идей Алана Тьюринга.

¶Биография

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

В 1944 году, в возрасте 16 лет, он поступил в Городской колледж Нью-Йорка (City College of New York), где в 1948 году получил степень бакалавра по математике. Продолжил обучение в Принстонском университете, где в 1950 году под руководством Алонзо Чёрча защитил докторскую диссертацию на тему «Арифметическая иерархия и неразрешимые проблемы». В диссертации Дэвис ввёл понятие арифметической иерархии — классификации подмножеств натуральных чисел по сложности их определимости в арифметике первого порядка.

После защиты Дэвис преподавал в Университете Иллинойса в Урбана-Шампейн (1950–1952), затем в Политехническом институте Бруклина (1952–1954). С 1954 года работал в Университете Нью-Йорка (New York University, NYU), где в 1965 году стал профессором. В 1974 году перешёл в Калифорнийский университет в Беркли, где проработал до выхода на пенсию в 1994 году.

¶Научные достижения

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

Наиболее известным вкладом Дэвиса является его работа над десятой проблемой Гильберта, сформулированной в 1900 году. Проблема требовала найти общий алгоритм, который по заданному диофантову уравнению (многочлену с целыми коэффициентами) определял бы, имеет ли оно решение в целых числах.

В 1953 году Дэвис предложил концепцию «диофантовых множеств» — множеств натуральных чисел, которые могут быть заданы диофантовыми уравнениями. Он показал, что любое перечислимое множество (множество, которое может быть сгенерировано алгоритмом) является диофантовым, при условии, что существует диофантово представление для экспоненциальной функции. Это утверждение стало известно как гипотеза Дэвиса.

В 1961 году Дэвис совместно с Хиллари Патнэмом и Джулией Робинсон доказали, что любое перечислимое множество может быть представлено как множество решений диофантова уравнения с экспоненциальной функцией (так называемое «экспоненциально-диофантово» представление). Этот результат, известный как теорема Дэвиса — Патнэма — Робинсон, стал ключевым шагом к окончательному решению проблемы.

В 1970 году, опираясь на работы Дэвиса, Патнэма и Робинсон, советский математик Юрий Матиясевич доказал, что экспоненциальная функция может быть выражена диофантовым образом, и тем самым завершил доказательство неразрешимости десятой проблемы Гильберта: общего алгоритма для определения разрешимости диофантовых уравнений не существует.

¶Теория алгоритмов и вычислимость

Дэвис внёс существенный вклад в развитие теории алгоритмов. В 1958 году он опубликовал книгу «Вычислимость и неразрешимость» (Computability and Unsolvability), которая стала классическим учебником по теории рекурсивных функций и машинам Тьюринга. В этой книге он впервые систематически изложил связь между формальными системами, алгоритмами и разрешимостью.

В 1970-х годах Дэвис активно занимался вопросами, связанными с тезисом Чёрча — Тьюринга, утверждающим, что любая интуитивно вычислимая функция может быть вычислена машиной Тьюринга. Он также участвовал в дискуссиях о природе вычислений и возможностях квантовых компьютеров, утверждая, что квантовые вычисления не могут превзойти классические по мощности в смысле разрешимости алгоритмических проблем.

¶Логика и основания математики

Дэвис внёс вклад в теорию моделей и теорию доказательств. Он разработал метод «гипердиофантовых уравнений» и исследовал связи между арифметической иерархией и иерархией проективных множеств. В 1970-х годах он совместно с Робертом Соловеем и другими математиками работал над проблемами, связанными с аксиомой выбора и континуум-гипотезой.

¶Педагогическая деятельность

Дэвис был известен как выдающийся педагог и популяризатор математики. Он написал несколько учебников, ставших стандартными в университетских курсах:

«Прикладная нелинейная математика» (Applied Nonstandard Analysis, 1977) — введение в нестандартный анализ, основанный на идеях Абрахама Робинсона.
«Математическая логика» (Mathematical Logic, 1977, совместно с Э. Дж. Вейраухом) — учебник, охватывающий теорию доказательств, теорию моделей и теорию вычислимости.
«Машины Тьюринга и вычислимость» (Turing Machines and Computability, 1990) — популярное изложение основ теории алгоритмов.

Дэвис также активно участвовал в создании образовательных программ по информатике и математике в Калифорнийском университете в Беркли.

¶Признание и награды

Член Американской академии искусств и наук (с 1975).
Член Национальной академии наук США (с 1982).
Премия Лероя П. Стила (Steele Prize) Американского математического общества (2005) за выдающийся вклад в математическую логику и теорию вычислимости.
Премия за выдающиеся заслуги в области математики (Lifetime Achievement Award) от Ассоциации символической логики (2012).

¶Личная жизнь

Мартин Дэвис был женат на Вирджинии Дэвис (урождённой Либерман), с которой прожил более 60 лет. У них родилось двое детей. В свободное время Дэвис увлекался музыкой, играл на фортепиано и коллекционировал записи классической музыки. Он скончался 1 января 2023 года в Беркли в возрасте 94 лет.

¶Основные публикации

Davis, M. (1950). «The arithmetical hierarchy and unsolvable problems». Annals of Mathematics, 52(2), 259–282.
Davis, M., Putnam, H., & Robinson, J. (1961). «The decision problem for exponential diophantine equations». Annals of Mathematics, 74(3), 425–436.
Davis, M. (1958). Computability and Unsolvability. McGraw-Hill.
Davis, M. (1977). Applied Nonstandard Analysis. John Wiley & Sons.
Davis, M., & Weyrauch, E. J. (1977). Mathematical Logic. Springer-Verlag.
Davis, M. (1990). Turing Machines and Computability. Springer-Verlag.

¶Интересные факты

Дэвис был одним из первых, кто осознал важность работ Алана Тьюринга для математической логики. В 1965 году он организовал специальный семинар в Нью-Йорке, посвящённый машинам Тьюринга и их приложениям.
В 2000 году Дэвис опубликовал статью «The Universal Computer: The Road from Leibniz to Turing», в которой проследил историю развития идей о вычислимости от Лейбница до Тьюринга.
Дэвис был активным сторонником использования формальных методов в информатике и часто выступал с критикой чрезмерно упрощённых подходов к программированию.

¶Источники

Davis, M. (2000). The Universal Computer: The Road from Leibniz to Turing. W. W. Norton & Company.
Matiyasevich, Y. (1993). Hilbert’s Tenth Problem. MIT Press.
Стил, Л. (2005). «Martin Davis: A Life in Logic». Notices of the American Mathematical Society, 52(10), 1184–1192.
Некролог Мартина Дэвиса в The New York Times, 10 января 2023 года.
Биографические данные из архива Калифорнийского университета в Беркли.