Loading article…
エミール・レオン・ポスト（/ p oʊ st /、1897年2月11日 - 1954年4月21日）は、アメリカの数学者、論理学者。彼は、後に計算可能性理論として知られるようになる分野での業績で最もよく知られている。
ポストは、ロシア帝国（現在のポーランド）ポーランド会議領スヴァウキ県アウグストゥフで、1904年5月にニューヨーク市に移住したポーランド系ユダヤ人の家庭に生まれた。両親はアーノルドとパール・ポストである。[ 2 ]
ポストは天文学に興味を持っていたが、12歳の時に自動車事故で左腕を失った。この喪失はプロの天文学者になる上で大きな障害となり、天文学ではなく数学を専攻する決断につながった。[ 3 ]
ポストはタウンゼント・ハリス高校に通い、その後ニューヨーク市立大学に進学し、1917年に数学の理学士号を取得して卒業した。[ 1 ]
1920年にコロンビア大学でカシウス・ジャクソン・キーザーの指導の下、数学の博士号を取得した後、1920年から1921年の学年度にプリンストン大学で博士研究員として研究を行った。その後、ポストはニューヨーク市の高校で数学教師となった。
ポストは1929年にガートルード・シンガー（1900年 - 1956年）と結婚し、娘のフィリス・ポスト・グッドマン（1932年 - 1995年）をもうけた。[ 4 ]ポストはプリンストン大学在学中から経験していた躁病発作を避けるため、医師の助言に従い、研究に費やす時間は1日最大3時間とした。[ 5 ]
1936年、彼はニューヨーク市立大学の数学科に任命された。彼はうつ病の電気ショック療法後に心臓発作を起こし、1954年4月に亡くなった。[ 5 ] [ 6 ]
ポストは、後に短縮されて『初等命題の一般理論入門』（1921年）として出版された博士論文の中で、とりわけ『プリンキピア・マテマティカ』の命題論理が完全であることを証明した。すなわち、『プリンキピア・マテマティカ』の公理と置換規則およびモーダス・ポネンス規則が与えられれば、すべてのトートロジーは定理となる。ポストはまた、C・S・パースやルートヴィヒ・ヴィトゲンシュタインとは独立に真理値表を考案し、それを数学的に有効活用した。ジャン・ヴァン・ヘイエノールトの数理論理学に関する有名な参考書（1966年）には、これらの結果をまとめたポストの1921年の古典的な論文が再録されている。
プリンストン大学在学中、ポストは『プリンキピア・マテマティカ』の不完全性を発見する寸前まで迫ったが、これは1931年にクルト・ゲーデルによって証明された。ポストは当初、自分の考えが受け入れられるためには「完全な解析」が必要だと考えていたため、その考えを発表しなかった。[ 2 ]ポストは1938年にゲーデルに宛てた絵葉書の中で次のように述べている。
1936年、ポストはアラン・チューリングとは独立して、チューリングマシンモデルと本質的に同等の計算の数学モデルを開発した。彼はこれを同等の能力を持ちながら複雑さが増していく一連のモデルの最初のものとして、論文に「Formulation 1」というタイトルを付けた。このモデルは「ポストのマシン」またはポスト・チューリングマシンと呼ばれることもあるが、ポストのタグマシンやその他の特殊な種類のポスト正準システムと混同してはならない。ポスト正準システムは文字列書き換えを使用する計算モデルで、1920年代にポストによって開発され、1943年に初めて発表された。ポストの書き換え技術は現在、プログラミング言語の仕様と設計で広く使われており、チャーチのラムダ計算と同様に、古典的な現代論理が実用的な計算に及ぼした顕著な影響である。ポストは「補助記号」の方法を考案し、それによって任意のポスト生成言語、そして実際には任意の計算可能な関数や計算可能な集合を正準的に表現することができた。
対応システムは、決定不能性の簡単な例を示すために、1946年にポストによって導入されました。[ 8 ]彼は、制約を満たすポスト対応問題（PCP）は一般に決定不能であることを示しました。対応問題の決定不能性は、形式言語の理論で決定不能性の結果を得るためにまさに必要なものであることがわかりました。
1944年にアメリカ数学会で行った影響力のある講演の中で、彼はチューリング次数が停止問題のチューリング次数よりも小さい、計算不可能な再帰的に列挙可能な集合の存在という問題を提起した。この問題は「ポストの問題」として知られるようになり、多くの研究を刺激した。そして1950年代に、計算可能性理論における強力な優先性法の導入によって、この問題は肯定的に解決された。
ポストは1940年に発表した長編論文で、多項群（n項群）の理論に根本的かつ今なお影響力のある貢献をした。彼の主要な定理は、多項群は群の正規部分群の要素の反復積であり、商群は位数n - 1の巡回群であることを示した。彼はまた、集合上の多項群演算は、同じ集合上の群演算で表現できることも示した。この論文には他にも多くの重要な結果が含まれている。