数学とコンピュータ・サイエンス
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/03 07:38 UTC 版)
「ヒラリー・パトナム」の記事における「数学とコンピュータ・サイエンス」の解説
パトナムは自身の哲学的仕事とは直接には関係ない科学分野にも貢献を果たしている。数学者としてパトナムはヒルベルトのいわゆる第10問題の解決に一役買った。ユーリ・マチャセビッチは1970年に、ディオファントス方程式の任意の系（整数を係数とする多項式）が整数において解をもつかを決定する一般的なアルゴリズムがあるのかどうかという問題に答えるため、フィボナッチ数を用いた定理を案出した。ところでパトナムとマーティン・ディヴィス、また彼らとは別にジュリア・ロビンソンは、マチャセビッチの定理がこのような一般アルゴリズムが存在し得ないことを証明するに十分であることをすでに証明していた。こうして第10問題には解法がないことが証明された。 パトナムはコンピュータ・サイエンスの分野ではマーティン・ディヴィスと共に充足可能性問題(SAT)の解法を与えるデービス・パトナムのアルゴリズムを開発したことで知られる。このアルゴリズムは、任意のブール論理式の各変数について、式全体の値が真になるような真ないし偽の値の組み合わせが存在するかどうかを発見するものである。1962年にディヴィスとパトナムはジョージ・ロッジマンとドナルド・W・ラヴランドの協力を得てこのアルゴリズムをさらに精密にし、現在DPLLアルゴリズムの名前で知られるものが完成した。このアルゴリズムは効率的で、今日もなお最も完全なSATソルバー（充足可能性問題の解法）の基礎となっている。
※この「数学とコンピュータ・サイエンス」の解説は、「ヒラリー・パトナム」の解説の一部です。
「数学とコンピュータ・サイエンス」を含む「ヒラリー・パトナム」の記事については、「ヒラリー・パトナム」の概要を参照ください。
- 数学とコンピュータ・サイエンスのページへのリンク
