エミール・ポスト

エミール・レオン・ポスト（、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. エミール・ポストを直接知る者として言及あり。

19世紀アメリカ合衆国の哲学者
20世紀アメリカ合衆国の哲学者
970211
-970211
19世紀の論理学者
20世紀の論理学者
アメリカ合衆国の論理学者
計算可能性理論の研究者
ニューヨーク市立大学シティカレッジの教員
コロンビア大学出身の人物
ロシア帝国のユダヤ人
東欧ユダヤ系アメリカ人
スヴァルキ県出身の人物
1897年生
1954年没
数学に関する記事
ニューヨーク州の数学者