Мартин Дэвис (математик)

Мартин Дэвис
Мартин Дэвис
	Дэвис в 1996 году
Рожденный	Мартин Дэвид Дэвис ; 8 марта 1928 г. ; Нью-Йорк , США
Умер	1 января 2023 г. (94 года) ; Беркли, Калифорния , США
Альма-матер	Городской колледж Нью-Йорка ( AB ) ; Принстонский университет ( доктор философии )
Известный	Алгоритм Дэвиса – Патнэма ; Алгоритм ДПЛЛ ; Работа над десятой проблемой Гильберта. ;
Супруг	Вирджиния Уайтфорд Палмер ( м. 1951)
Награды	Премия Шовене (1975).
	Научная карьера
Учреждения	Белл Лаборатории ; РЭНД Корпорация ; Нью-Йоркский университет ; Калифорнийский университет, Беркли ;
Диссертация	О теории рекурсивной неразрешимости (1950)
Докторантура	Церковь Алонсо
Докторанты	Моше Коппель ; Дональд В. Лавленд ;

Мартин Дэвид Дэвис (8 марта 1928 — 1 января 2023) — американский математик и учёный-компьютерщик , внесший вклад в области теории вычислимости и математической логики . Его работа над десятой проблемой Гильберта привела к теореме MRDP . Он также усовершенствовал модель Пост-Тьюринга и стал соавтором алгоритма Дэвиса-Патнэма-Логеманна-Лавленда (DPLL) , который является основой для решателей булевой выполнимости .

Дэвис получил премию Лероя П. Стила , премию Шовене (совместно с Рубеном Хершем ) и премию Лестера Р. Форда . Он был членом Американской академии искусств и наук и членом Американского математического общества .

Ранняя жизнь и образование

Родители Дэвиса были еврейскими иммигрантами в США из Лодзи , Польша, и поженились после того, как снова встретились в Нью-Йорке. Дэвис родился в Нью-Йорке 8 марта 1928 года. Он вырос в Бронксе , где родители поощряли его получить полное образование. ^{[ 1 ]}^{[ 2 ]} Он окончил престижную Высшую научную школу Бронкса в 1944 году и получил степень бакалавра математики в Городском колледже в 1948 году и докторскую степень в Принстонском университете в 1950 году. ^{[ 3 ]} Его докторскую диссертацию под названием « О теории рекурсивной неразрешимости » курировал американский математик и учёный-компьютерщик Алонзо Чёрч . ^{[ 1 ]}^{[ 2 ]}^{[ 4 ]}

Академическая карьера

Во время исследовательской работы в Университете Иллинойса в Урбана-Шампейн в начале 1950-х годов он присоединился к лаборатории систем управления и стал одним из первых программистов ORDVAC . ^{[ 1 ]} Позже он работал в Bell Labs и RAND Corporation, прежде чем поступить в Нью-Йоркский университет . ^{[ 1 ]} Во время своего пребывания в Нью-Йоркском университете он помог создать в университете факультет компьютерных наук. Он ушел из Нью-Йоркского университета в 1996 году. ^{[ 3 ]}^{[ 1 ]} Позже он был членом приглашенного факультета Калифорнийского университета в Беркли . ^{[ 5 ]}

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

Дэвис впервые работал над десятой проблемой Гильберта во время своей докторской диссертации, работая с Алонзо Чёрчем. Теорема, сформулированная немецким математиком Давидом Гильбертом , задает вопрос: существует ли для диофантова уравнения алгоритм, который может решить, разрешимо ли это уравнение? ^{[ 1 ]} В диссертации Дэвиса была выдвинута гипотеза о неразрешимости проблемы. В 1950-х и 1960-х годах Дэвис вместе с американскими математиками Хилари Патнэм и Джулией Робинсон добились прогресса в решении этой гипотезы. Доказательство гипотезы было окончательно завершено в 1970 году работой русского математика Юрия Матиясевича . Это привело к появлению MRDP или теоремы DPRM , названной в честь Дэвиса, Патнэма, Робинсона и Матиясевича. ^{[ 1 ]} Описывая проблему, Дэвис ранее упомянул, что, когда он был студентом, он находил эту проблему «непреодолимо соблазнительной», а позже она постепенно стала его «навязчивой идеей на всю жизнь». ^{[ 6 ]}

Другие вклады

Дэвис сотрудничал с Патнэмом, Джорджем Логеманом и Дональдом В. Лавлендом в 1961 году, чтобы представить алгоритм Дэвиса-Патнэма-Логеманна-Лавленда (DPLL) , который представлял собой полный для обратного отслеживания на основе алгоритм поиска определения выполнимости формул пропозициональной логики в конъюнктивных нормальной форме , т.е. для решения задачи CNF-SAT . ^{[ 7 ]} Алгоритм представлял собой усовершенствование более раннего алгоритма Дэвиса-Патнэма , который представлял собой процедуру, основанную на разрешении, разработанную Дэвисом и Патнэмом в 1960 году. ^{[ 8 ]}^{[ 9 ]} Алгоритм лежит в основе архитектуры быстрых решателей булевой выполнимости. ^{[ 6 ]}

Помимо своей работы по теории вычислимости , Дэвис также внес значительный вклад в области вычислительной сложности и математической логики . ^{[ 1 ]}^{[ 6 ]}^{[ 10 ]} Дэвис был также известен своей моделью машин Пост-Тьюринга . ^{[ 3 ]}

В 1974 году Дэвис получил премию Лестера Р. Форда за пояснительные статьи, связанные с его работой над десятой проблемой Гильберта: ^{[ 2 ]}^{[ 11 ]} а в 1975 году он выиграл премию Лероя П. Стила и премию Шовене (совместно с Рубеном Хершем ). ^{[ 12 ]} он стал членом Американской академии искусств и наук . В 1982 году ^{[ 2 ]} а в 2013 году он был выбран одним из первых членов Американского математического общества . ^{[ 13 ]}

Книга Дэвиса 1958 года «Вычислимость и неразрешимость» считается классикой теоретической информатики , а его книга 2000 года «Универсальный компьютер» прослеживает эволюцию и историю вычислений, начиная с работ Готфрида Вильгельма Лейбница и Алана Тьюринга . ^{[ 1 ]} Его книга «Неразрешимое» , первое издание которой вышло в 1965 году, представляла собой сборник неразрешимых задач и вычислимых функций . ^{[ 6 ]}

Личная жизнь и смерть

Дэвис был женат на Вирджинии Уайтфорд Палмер, художнице по текстилю. Пара познакомилась во время своего пребывания в районе Урбана-Шампейн и впоследствии поженилась в 1951 году. ^{[ 14 ]}^: 8 У них было двое детей. ^{[ 3 ]} После выхода на пенсию пара жила в Беркли, Калифорния . ^{[ 1 ]}

Дэвис умер 1 января 2023 года в возрасте 94 лет. ^{[ 15 ]} Его жена умерла в тот же день, несколько часов спустя. ^{[ 16 ]}

Избранные публикации

Книги

Дэвис, Мартин (1958). Вычислимость и неразрешимость . Нью-Йорк: Дувр. ISBN 0-486-61471-9 . Дуврское переиздание
Дэвис, Мартин (1977). Прикладной нестандартный анализ . Нью-Йорк: Уайли. ISBN 9780471198970 . Переиздание Дувра, 2014 г.
Дэвис, Мартин; Вейкер, Элейн Дж .; Сигал, Рон (1994). Вычислимость, сложность и языки: основы теоретической информатики (2-е изд.). Бостон: Academic Press, Harcourt, Brace. ISBN 9780122063824 .
Дэвис, Мартин (2000). Универсальный компьютер: путь от Лейбница к Тьюрингу . Нортон. ISBN 0393047857 . Перепечатано как Логические машины: математики и происхождение компьютера . Нью-Йорк: Нортон. 2000. ISBN 9780393322293 .
Дэвис, Мартин (2004). Неразрешимое: Основные статьи о неразрешимых предложениях, неразрешимых проблемах и вычислимых функциях . Нью-Йорк: Dover Publications. ISBN 0-486-43228-9 . OCLC 53840050 .

Статьи

Дэвис, Мартин (1973), «Десятая проблема Гильберта неразрешима», The American Mathematical Monthly , 80 (3), 233–269. дои : 10.1080/00029890.1973.11993265 .
Дэвис, Мартин (1995), «Является ли математическое понимание алгоритмическим?», Поведенческие науки и науки о мозге , 13 (4), 659–60.
Дэвис, Мартин (2020), «Семьдесят лет информатики» , В: Бласс А. , Цегельски П., Дершовиц Н. , Дросте М., Финкбайнер Б. (ред.) Области логики и вычислений III , 105–117 . Конспекты лекций по информатике, том. 12180. Шпрингер: Чам, Швейцария. дои : 10.1007/978-3-030-48006-6_8 .

См. также

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Джексон, Аллин (сентябрь 2007 г.), «Интервью с Мартином Дэвисом» (PDF) , Уведомления Американского математического общества , том. 55, нет. 5, Провиденс, Род-Айленд: Американское математическое общество (опубликовано в мае 2008 г.), стр. 560–571, ISSN 0002-9920 , OCLC 1480366 .
^ Jump up to: ^а ^б ^с ^д О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф. , «Мартин Дэвис (математик)» , Архив истории математики MacTutor , Университет Сент-Эндрюс
^ Jump up to: ^а ^б ^с ^д «Мартин Дэвис – Биография» . История математики . Проверено 8 января 2023 г.
^ Мартин Дэвис в проекте «Математическая генеалогия»
^ «Мартин Дэвис | Кафедра математики Калифорнийского университета в Беркли» . math.berkeley.edu . Проверено 8 января 2023 г.
^ Jump up to: ^а ^б ^с ^д Мартин Дэвис о вычислимости, вычислительной логике и математических основах . Выдающийся вклад в логику. Том. 10. 2016. doi : 10.1007/978-3-319-41842-1 . ISBN 978-3-319-41841-4 .
^ «Информатика – Техасский университет CS395T, весна 2011 г.» (PDF) .
^ «Алгоритм Дэвиса – Патнэма» . hellenicaworld.com . Проверено 8 января 2023 г.
^ «Алгоритм DPLL – логика обучения для информатики» . logic4free.informatik.uni-kiel.de . Проверено 8 января 2023 г.
^ «Новые и заслуживающие внимания издания на нашей книжной полке» (PDF) . Американское математическое общество — Уведомления об AMS . 1 декабря 2017. с. 1327 . Проверено 7 января 2023 г.
^ Дэвис, Мартин (1973). «Десятая проблема Гильберта неразрешима» . амер. Математика. Ежемесячно . 80 (3): 233–269. дои : 10.2307/2318447 . JSTOR 2318447 .
^ Дэвис, Мартин; Херш, Рубен (1973). «10-я проблема Гильберта». Научный американец . 229 (5). ООО «Спрингер Сайенс энд Бизнес Медиа»: 84–91. Бибкод : 1973SciAm.229e..84D . doi : 10.1038/scientificamerican1173-84 . ISSN 0036-8733 .
^ Список членов Американского математического общества . Проверено 17 марта 2014 г.
^ Омодео, Э.Г., и Поликрити, А., ред., Мартин Дэвис о вычислимости, вычислительной логике и математических основах ( Берлин / Гейдельберг : Springer , 2016), стр. 8 .
^ «Мартин Дэвид Дэвис» . Похоронное бюро Харриса . Проверено 4 января 2023 г.
^ «Вспоминая Мартина и Вирджинию Дэвис» . Проверено 8 января 2023 г.

Внешние ссылки

Официальный сайт
Празднование Эмиля Поста и его «неразрешимой проблемы» Tag: 100 Years Later на YouTube, включая материалы Мартина Дэвиса (запись длится 1 час 39 минут)
Мартин Дэвис: универсальность вездесуща (Princeton Academics) на YouTube
«Памяти Мартина Дэвиса» (PDF) . Уведомления Американского математического общества . 71 (7): 898–907. Август 2024 г. doi : 10.1090/noti2982 .

[jackson-1] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Джексон, Аллин (сентябрь 2007 г.), «Интервью с Мартином Дэвисом» (PDF) , Уведомления Американского математического общества , том. 55, нет. 5, Провиденс, Род-Айленд: Американское математическое общество (опубликовано в мае 2008 г.), стр. 560–571, ISSN 0002-9920 , OCLC 1480366 .

[mactutor-2] Jump up to: ^а ^б ^с ^д О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф. , «Мартин Дэвис (математик)» , Архив истории математики MacTutor , Университет Сент-Эндрюс

[:0-3] Jump up to: ^а ^б ^с ^д «Мартин Дэвис – Биография» . История математики . Проверено 8 января 2023 г.

[4] Мартин Дэвис в проекте «Математическая генеалогия»

[5] «Мартин Дэвис | Кафедра математики Калифорнийского университета в Беркли» . math.berkeley.edu . Проверено 8 января 2023 г.

[:2-6] Jump up to: ^а ^б ^с ^д Мартин Дэвис о вычислимости, вычислительной логике и математических основах . Выдающийся вклад в логику. Том. 10. 2016. doi : 10.1007/978-3-319-41842-1 . ISBN 978-3-319-41841-4 .

[7] «Информатика – Техасский университет CS395T, весна 2011 г.» (PDF) .

[8] «Алгоритм Дэвиса – Патнэма» . hellenicaworld.com . Проверено 8 января 2023 г.

[9] «Алгоритм DPLL – логика обучения для информатики» . logic4free.informatik.uni-kiel.de . Проверено 8 января 2023 г.

[10] «Новые и заслуживающие внимания издания на нашей книжной полке» (PDF) . Американское математическое общество — Уведомления об AMS . 1 декабря 2017. с. 1327 . Проверено 7 января 2023 г.

[11] Дэвис, Мартин (1973). «Десятая проблема Гильберта неразрешима» . амер. Математика. Ежемесячно . 80 (3): 233–269. дои : 10.2307/2318447 . JSTOR 2318447 .

[Davis_Hersh_Hilbert_10th-12] Дэвис, Мартин; Херш, Рубен (1973). «10-я проблема Гильберта». Научный американец . 229 (5). ООО «Спрингер Сайенс энд Бизнес Медиа»: 84–91. Бибкод : 1973SciAm.229e..84D . doi : 10.1038/scientificamerican1173-84 . ISSN 0036-8733 .

[13] Список членов Американского математического общества . Проверено 17 марта 2014 г.

[14] Омодео, Э.Г., и Поликрити, А., ред., Мартин Дэвис о вычислимости, вычислительной логике и математических основах ( Берлин / Гейдельберг : Springer , 2016), стр. 8 .

[15] «Мартин Дэвид Дэвис» . Похоронное бюро Харриса . Проверено 4 января 2023 г.

[16] «Вспоминая Мартина и Вирджинию Дэвис» . Проверено 8 января 2023 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

Базы данных авторитетного контроля
International	FAST ISNI VIAF WorldCat
National	Norway Spain France BnF data Catalonia Germany Italy Israel Belgium United States Latvia Japan Czech Republic Greece Korea Croatia Netherlands
Academics	Association for Computing Machinery CiNii 2 DBLP MathSciNet Mathematics Genealogy Project zbMATH
People	Trove
Other	SNAC IdRef