エミール・ポスト
エミール・レオン・ポスト（英: Emil Leon Post、1897年2月11日 - 1954年4月21日）は、アメリカ合衆国の数学者、論理学者。 経歴ユダヤ系ポーランド人の家庭に生まれ、幼いころにアメリカ合衆国に移住。コロンビア大学で数学の博士号を取得すると、ポストドクターとしてプリンストン大学へ。プリンストンでは Principia Mathematica の不完全性の発見に非常に近いところまでいった（1931年にクルト・ゲーデルが証明）。その後、ニューヨークで高校の数学教師となる。1936年、ニューヨークのシティカレッジの数学科で職を得て、亡くなるまで務めた。 コロンビア大学での博士論文で、ポストは他の様々なことと同時に Principia Mathematica の命題計算が完全であること（Principia の公理と置換規則とモーダスポネンスを与えられたとき、全ての恒真式は定理であること）を証明した。また、ルートヴィヒ・ウィトゲンシュタインやチャールズ・サンダース・パースとは独立に真理値表を考案した。 再帰理論1936年、ポストはアラン・チューリングとは独立に、チューリングマシンと基本的に等価な計算の数学的モデルを考案した。これを一連の等価な能力を持つモデルの第一例にしようと考え、ポストは論文に Formulation 1 という題名をつけた（このモデルは「ポストの機械」あるいはポスト＝チューリング機械と呼ばれる。タグシステムなどのポスト正準系とは異なる。ポスト正準系はポストが1920年代に考案した文字列書き換え系に基づく計算モデルで、1943年に発表された）。 ポストの対応問題の非可解性は、形式言語理論の非可解性に正確に対応していることがわかっている。 1944年、ポストはアメリカ数学会で、停止性問題よりもチューリング次数が低い計算不可能な帰納的可算集合が存在するかという問題を提起した。これはポストの問題と呼ばれ、様々な研究を喚起した。これは1950年代に肯定的に解決し、その研究の過程で再帰理論が発展した。 主な論文
関連項目参考文献
外部リンク
|
||||||||||||||||||||||||||
.svg){kind=small}
Portal di Ensiklopedia Dunia
