Loading article…
マーティン・デイヴィッド・デイヴィス（1928年3月8日 - 2023年1月1日）は、計算可能性理論と数理論理学の分野に貢献したアメリカの数学者、コンピュータ科学者である。ヒルベルトの第10問題に関する彼の研究は、MRDP定理につながった。彼はまた、ポスト・チューリング・モデルを発展させ、ブール充足可能性ソルバーの基礎となるデイヴィス・パトナム・ロゲマン・ラブランド（DPLL）アルゴリズムを共同開発した。
デイビスは、リロイ・P・スティール賞、ショーヴネ賞（ルーベン・ハーシュと共同受賞）、レスター・R・フォード賞を受賞した。彼はアメリカ芸術科学アカデミーのフェローであり、アメリカ数学会のフェローでもあった。
デイビスの両親はポーランドのウッチから米国に移住してきたユダヤ系移民で、ニューヨーク市で再会した後結婚した。デイビスは1928年3月8日にニューヨーク市で生まれた。彼はブロンクスで育ち、両親は彼に十分な教育を受けるよう勧めた。[ 1 ] [ 2 ]彼は1944年に名門ブロンクス科学高校を卒業し、 1948年にシティカレッジで数学の学士号を、 1950年にプリンストン大学で博士号を取得した。 [ 3 ]彼の博士論文「再帰的不可解性の理論について」は、アメリカの数学者でコンピュータ科学者のアロンゾ・チャーチの指導を受けた。[ 1 ] [ 2 ] [ 4 ]
1950年代初頭、イリノイ大学アーバナ・シャンペーン校で研究講師を務めていた際、彼は制御システム研究所に加わり、 ORDVACの初期プログラマーの一人となった。[ 1 ]その後、ベル研究所とランド研究所で働き、ニューヨーク大学に加わった。[ 1 ]ニューヨーク大学在籍中、彼は同大学のコンピュータサイエンス学科の設立に尽力した。1996年にニューヨーク大学を退職した。[ 3 ] [ 1 ]その後、カリフォルニア大学バークレー校の客員教員を務めた。[ 5 ]
デイビスは、アロンゾ・チャーチと共同で博士論文を執筆中に、ヒルベルトの第10問題に初めて取り組みました。ドイツの数学者デイヴィッド・ヒルベルトが提起したこの定理は、ディオファントス方程式が与えられたとき、その方程式が解けるかどうかを判定できるアルゴリズムが存在するか、という問いを投げかけています。 [ 1 ]デイビスの博士論文では、この問題は解けないという予想が提示されました。1950年代と1960年代に、デイビスはアメリカの数学者ヒラリー・パトナムとジュリア・ロビンソンと共に、この予想の解決に向けて進展を遂げました。この予想の証明は、ロシアの数学者ユーリ・マティヤセヴィチの研究により、1970年にようやく完成しました。これにより、デイビス、パトナム、ロビンソン、マティヤセヴィチの名にちなんで名付けられたMRDPまたはDPRM定理が生まれました。 [ 1 ]デイビスは以前、この問題について、学部生の頃に「抗いがたいほど魅力的」だと感じ、その後次第に「生涯の執着」になったと述べていた。[ 6 ]
デイビスは1961年にパトナム、ジョージ・ロゲマン、ドナルド・W・ラブランドと共同で、連言標準形命題論理式の充足可能性を判定するための完全なバックトラッキングベースの探索アルゴリズムであるデイビス・パトナム・ロゲマン・ラブランド（DPLL）アルゴリズムを導入した。これは、CNF-SAT問題を解くためのものである。[ 7 ]このアルゴリズムは、 1960年にデイビスとパトナムによって開発された、分解ベースの手順である以前のデイビス・パトナムアルゴリズムの改良版である。 [ 8 ] [ 9 ]このアルゴリズムは、高速ブール充足可能性ソルバーのアーキテクチャの基礎となっている。 [ 6 ]
デイビスは計算可能性理論の研究に加えて、計算複雑性や数理論理学の分野にも大きな貢献をした。[ 1 ] [ 6 ] [ 10 ]デイビスはポストチューリングマシンのモデルでも知られていた。[ 3 ]
1974年、デイビスはヒルベルトの第10問題に関する解説書でレスター・R・フォード賞を受賞し[ 2 ] [ 11 ] 、1975年にはルロイ・P・スティール賞とショーヴネ賞（ルーベン・ハーシュと共同受賞）を受賞した[ 12 ] 。 1982年にはアメリカ芸術科学アカデミーのフェローとなり[ 2 ] 、2013年にはアメリカ数学会の初代フェローの一人に選ばれた[ 13 ]。
デイビスの1958年の著書『計算可能性と解決不可能性』は理論計算機科学の古典とみなされており、2000年の著書『ユニバーサルコンピュータ』はゴットフリート・ヴィルヘルム・ライプニッツからアラン・チューリングまでの計算機の進化と歴史をたどっている。[ 1 ] 1965年に初版が出版された彼の著書『決定不可能なもの』は、解決不可能な問題と計算可能な関数のコレクションだった。[ 6 ]
デイビスは、テキスタイルアーティストのバージニア・ホワイトフォード・パーマーと結婚した。二人はアーバナ・シャンペーン地域で出会い、その後1951年に結婚した。 [ 14 ] : 8二人の間には2人の子供がいた。[ 3 ]デイビスの引退後、二人はカリフォルニア州バークレーに住んでいた。 [ 1 ]
本
記事
