エミール・ポスト
| エミール・レオン・ポスト | |
|---|---|
 | |
| 生誕 |
1897年2月11日 ロシア帝国（現： ポーランド）アウグストゥフ |
| 死没 |
1954年4月21日.svg){kind=small} アメリカ合衆国 ニューヨーク |
| 研究分野 | 数学 |
| 出身校 | コロンビア大学 |
| 主な業績 |
Formulation 1 ポストの対応問題 『数学原理』の命題計算の完全性証明 |
| プロジェクト:人物伝 | |
エミール・レオン・ポスト（英: Emil Leon Post、1897年2月11日 - 1954年4月21日）は、アメリカ合衆国の数学者、論理学者。
経歴
[編集]ユダヤ系ポーランド人の家庭に生まれ、幼いころにアメリカ合衆国に移住。コロンビア大学で数学の博士号を取得すると、ポストドクターとしてプリンストン大学へ。プリンストンでは Principia Mathematica の不完全性の発見に非常に近いところまでいった（1931年にクルト・ゲーデルが証明）。その後、ニューヨークで高校の数学教師となる。1936年、ニューヨークのシティカレッジの数学科で職を得て、亡くなるまで務めた。
コロンビア大学での博士論文で、ポストは他の様々なことと同時に Principia Mathematica の命題計算が完全であること（Principia の公理と置換規則とモーダスポネンスを与えられたとき、全ての恒真式は定理であること）を証明した。また、ルートヴィヒ・ウィトゲンシュタインやチャールズ・サンダース・パースとは独立に真理値表を考案した。
再帰理論
[編集]1936年、ポストはアラン・チューリングとは独立に、チューリングマシンと基本的に等価な計算の数学的モデルを考案した。これを一連の等価な能力を持つモデルの第一例にしようと考え、ポストは論文に Formulation 1 という題名をつけた（このモデルは「ポストの機械」あるいはポスト＝チューリング機械と呼ばれる。タグシステムなどのポスト正準系とは異なる。ポスト正準系はポストが1920年代に考案した文字列書き換え系に基づく計算モデルで、1943年に発表された）。
ポストの対応問題の非可解性は、形式言語理論の非可解性に正確に対応していることがわかっている。
1944年、ポストはアメリカ数学会で、停止性問題よりもチューリング次数が低い計算不可能な帰納的可算集合が存在するかという問題を提起した。これはポストの問題と呼ばれ、様々な研究を喚起した。これは1950年代に肯定的に解決し、その研究の過程で再帰理論が発展した。
主な論文
[編集]- 1936, "Finite Combinatory Processes - Formulation 1," Journal of Symbolic Logic 1: 103-105.
- 1943, "Formal Reductions of the General Combinatorial Decision Problem," American Journal of Mathematics 65: 197-215.
- 1944, "Recursively enumerable sets of positive integers and their decision problems," Bulletin of the American Mathematical Society 50: 284-316.
関連項目
[編集]参考文献
[編集]- Emil Leon Post Papers 1927-1991 - American Philosophical Society, Philadelphia, Pennsylvania.
- Davis, Martin (1993). The Undecidable (Ed.), pp. 288-406. Dover. ISBN 0-486-43228-9. Reprints several papers by Post.
- Davis, Martin (1994). "Emil L. Post: His Life and Work" in Davis, M., ed., Solvability, Provability, Definability: The Collected Works of Emil L. Post. Birkhäuser: xi--xxviii. A biographical essay.
外部リンク
[編集]- O'Connor, John J. & Robertson, Edmund F., "Emil Leon Post", MacTutor History of Mathematics archive
- Emil Post、at the Mathematics Genealogy Project
- An interview with Martin Davis - Notices of the AMS, May 2008. エミール・ポストを直接知る者として言及あり。
