エミール・レオン・ポスト
【英】Emil Leon Post, Emil Post
エミール・レオン・ポストとは、アラン・チューリング（A.M.Turing）と共に、チューリングマシン（Post-Turing machine）を考案したことで知られる数学者である（ポストとチューリングはそれぞれ同時期に独立してチューリングマシンの概念を考案している）。1897年2月11日、ロシア帝国（現ポーランド）生まれ。1954年4月21日に米国ニューヨークで逝去した。
注）
弊社ではこのページで使用している画像の著作権は消失しているものと認識しております。万一、使用している画像の権利を所有しているという方がおられましたら、弊社にご連絡下さい。速やかに画像を外すか、正式な許可を得る手続きをしたいと思います。
エミール・ポスト
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/04/27 02:53 UTC 版)
ナビゲーションに移動 検索に移動| エミール・レオン・ポスト | |
|---|---|
 |
|
| 生誕 | 1897年2月11日 ロシア帝国（現： ポーランド）アウグストゥフ |
| 死没 | 1954年4月21日 アメリカ合衆国 ニューヨーク |
| 研究分野 | 数学 |
| 出身校 | コロンビア大学 |
| 主な業績 | 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. エミール・ポストを直接知る者として言及あり。
固有名詞の分類
- エミール・ポストのページへのリンク
