エミール・レオン・ポスト

エミール・レオン・ポスト
生まれる	1897年2月11日 アウグストゥフ、スヴァウキ県、ポーランド議会、ロシア帝国 （現ポーランド）
死亡	1954年4月21日(1954-04-21)（57歳） ニューヨーク市、米国
母校	ニューヨーク市立大学（BS、1917）[1] コロンビア大学（AM 1918、Ph.D. 1920）[2]
知られている	定式化1 ポスト対応問題プリンキピアの命題計算 の完全性証明ポストの反転公式ポストの格子ポストの定理
科学者としてのキャリア
フィールド	数学、論理
機関	プリンストン大学
論文	基本命題の一般理論入門 （1920年）
博士課程の指導教員	カシアス・ジャクソン・キーザー

エミール・レオン・ポスト（/ p oʊ s t / ; 1897年2月11日 - 1954年4月21日）は、アメリカの数学者、論理学者である。彼は、後に計算可能性理論として知られるようになった分野での研究で最もよく知られている。

ポストは、ロシア帝国（現在のポーランド）のポーランド領スヴァウキ県アウグストゥフで、1904年5月にニューヨーク市に移住したポーランド系ユダヤ人の家庭に生まれた。両親はアーノルド・ポストとパール・ポストである。^[2]

ポストは天文学に興味を持っていたが、12歳のときに自動車事故で左腕を失った。この喪失はプロの天文学者になる上で大きな障害となり、天文学ではなく数学を追求することを決意した。^[3]

ポストはタウンゼント・ハリス高校に通い、1917年にニューヨーク市立大学で数学の学士号を取得して卒業した。 ^[1]

1920年にコロンビア大学でカシアス・ジャクソン・ケイザーの指導の下で数学の博士号を取得した後、1920年から1921年にかけてプリンストン大学で博士研究員として研究を行った。その後、ポストはニューヨーク市の高校で数学の教師になった。

ポストは1929年にガートルード・シンガーと結婚し、娘フィリス・ポスト・グッドマン（1932年 - 1995年）をもうけた。^[4]ポストはプリンストン大学在学中から躁病発作に悩まされていたが、医師の助言に従い、1日最大3時間を研究に費やしていた。^[5]

1936年、彼はニューヨーク市立大学の数学科に任命された。1954年4月、うつ病の電気ショック療法後の心臓発作で亡くなった。^{[5] [6]}アラン・チューリングの死の2か月弱前であった。享年57歳。

ポストは博士論文（後に短縮されて「基本命題の一般理論入門」（1921年）として出版された）で、とりわけプリンキピア・マテマティカの命題論理が完全であることを証明した。つまり、プリンキピアの公理と置換規則および可能性規則が与えられれば、すべてのトートロジーは定理である。ポストはまた、CS パースやルートヴィヒ・ヴィトゲンシュタインとは独立して真理値表を考案し、それを数学的に有効に利用した。ジャン・ファン・ヘイエノールトの有名な数理論理学の参考書（1966年）には、これらの結果を述べたポストの1921年の古典的な論文が再録されている。

プリンストン在学中、ポストはプリンキピア・マテマティカの不完全性を発見する寸前まで行き、 1931年にクルト・ゲーデルがそれを証明した。ポストは当初、自分の考えが受け入れられるためには「完全な分析」が必要だと考え、出版しなかった。^[2]ポストは1938年にゲーデルに宛てたポストカードで次のように述べている。

もし私がゲーデルだったら、1921年にゲーデルの定理を発見していただろう。^[7]

1936 年、ポストはアラン チューリングとは独立して、本質的にチューリング マシンモデルと同等の計算の数学的モデルを開発した。彼はこれを、同等の能力を持ちながらも複雑さを増していく一連のモデルの最初のものとして意図し、論文に「定式化 1 」というタイトルを付けた。このモデルは「ポストのマシン」またはポスト チューリング マシンと呼ばれることもあるが、ポストのタグ マシンやその他の特殊なポスト カノニカル システムと混同しないようにする必要がある。ポスト カノニカル システムとは、1920 年代にポストによって開発され、1943 年に初めて公開された文字列書き換えを使用する計算モデルである。ポストの書き換え手法は、現在ではプログラミング言語の仕様と設計に広く浸透しており、チャーチのラムダ計算とともに、古典的現代論理が実用的なコンピューティングに与えた顕著な影響である。ポストは「補助記号」という手法を考案し、これによってあらゆるポスト生成言語、さらにはあらゆる計算可能な関数や集合をカノニカルに表現できるようになった。

対応システムは、決定不能性の簡単な例として1946年にポストによって導入されました。^[8]彼は、制約を満たすポスト対応問題（PCP）は一般に決定不能であることを示しました。対応問題の決定不能性は、形式言語理論で決定不能性の結果を得るためにまさに必要なものであることが判明しました。

1944年にアメリカ数学会で行った影響力のある演説で、彼は、チューリング次数が停止問題よりも小さい計算不可能な再帰的可算集合が存在するという問題を提起した。この問題はポストの問題として知られるようになり、多くの研究を刺激した。この問題は、 1950年代に計算可能性理論における強力な優先法の導入によって肯定的に解決された。

ポストは、1940 年に発表した長大な論文で、多項式群、つまりn項群の理論に根本的かつ現在でも影響力のある貢献をしました。彼の主要定理は、多項式群が群の正規部分群の要素の反復乗算であり、商群がn − 1の位数で巡回することを示しました。また、集合に対する多項式群の演算は、同じ集合に対する群の演算で表現できることも実証しました。この論文には、他にも多くの重要な結果が含まれています。

• ポスト、エミール・レオン (1919)。「一般化されたガンマ関数」。数学年報。第2シリーズ。20 ( 3): 202– 217。doi : 10.2307/ 1967871。JSTOR  1967871 。
• ポスト、エミール・レオン (1921)。「基本命題の一般理論入門」。アメリカ数学ジャーナル。43 (3): 163– 185。doi :10.2307/2370324。hdl : 2027 /uiuo.ark:/13960/t9j450f7q。JSTOR  2370324 。
• ポスト、エミール・レオン (1936)。「有限組み合わせプロセス - 定式化 1」。Journal of  Symbolic Logic。1 ( 3): 103– 105。doi :10.2307/2269031。JSTOR 2269031。S2CID 40284503  。
• ポスト、エミール・レオン (1940)。「多項式群」。アメリカ数学会誌。48 (2): 208– 350。doi : 10.2307/1990085。JSTOR  1990085 。
• ポスト、エミール・レオン(1943)。 「一般組合せ決定問題の形式的簡約」。アメリカ数学ジャーナル。65 (2): 197– 215。doi :10.2307/2371809。JSTOR  2371809。
• ポスト、エミール・レオン( 1944)。「正の整数の再帰的列挙集合とその決定問題」。アメリカ数学会報。50 (5): 284– 316。doi : 10.1090/s0002-9904-1944-08111-1。多対一削減という重要な概念を紹介します。

• 算術階層
• 機能の完全性
• 複数の発見のリスト
• コンピュータサイエンスの先駆者リスト

• スティルウェル、ジョン(2004)、「エミール・ポストとゲーデルとチューリングの先見」(PDF)、数学雑誌、77 (1): 3– 14、doi :10.2307/3219226、JSTOR  3219226
• Urquhart, Alasdair (2008)。「Emil Post」(PDF)。Gabbay, Dov M.、Woods, John Woods (編)。ラッセルから教会までの論理学。論理学の歴史ハンドブック。第 5 巻。Elsevier BV。
• Neary, Turlough (2015)、「バイナリ タグ システムにおける決定不能性と 5 組の単語の対応後問題」、コンピュータ サイエンスの理論的側面に関する国際シンポジウム、ライプニッツ国際情報学会議 (LIPIcs)、649 ～ 661 ページ、2015 年。

• アンシェル、アイリス・リー、アンシェル、マイケル（1993 年 11 月）。 「ポストマルコフ定理から決定問題を経て公開鍵暗号まで」。アメリカ数学月刊誌。100 ( 9 ) 。アメリカ数学協会：835～ 844。doi ：10.2307/2324657。JSTOR  2324657。

  エミール・ポストに捧げられたこの論文には、ポストに関する特別な資料が含まれています。これには、「ポストと同時代の暗号学および暗号学者との関係: ... 著名なゲーム理論家であり政治学者でもあるスティーブン・ブラムズ氏は、エミール・ポストの生涯と遺産は、20 世紀前半のニューヨークの知的生活の一側面を表しており、より深い調査が必要であると述べています。著者は、この論文がこの研究をさらに進めるのに役立つことを願っています」 (pp. 842–843) が含まれます。

• デイヴィス、マーティン編 (1993)。『The Undecidable』ドーバー、pp. 288–406。ISBN 0-486-43228-9。

  ポストによるいくつかの論文を再版します。

• デイビス、マーティン (1994)。「エミール L. ポスト: その生涯と業績」。解決可能性、証明可能性、定義可能性: エミール L. ポストの全集。ビルクハウザー。pp.  xi– xxviii。

  伝記エッセイ。

• ジャクソン、アリン（2008年5月）。「マーティン・デイビスとのインタビュー」AMSの通知。55 （5）：560-571。

  エミール・ポストに関する、彼の直接の記憶に基づく多くの資料。

• ジャクソン、アリン（2018年10月）。「エミール・ポスト：心理的忠実性」。推論：国際科学レビュー。doi ：10.37282/991819.18.48。S2CID  240012225。

  伝記記事。

• エミール・レオン・ポスト文書 1927-1991、アメリカ哲学協会、ペンシルベニア州フィラデルフィア。
• 「エミール・ポストと彼の「解決困難なタグ問題」を100年後に祝う」。YouTube。ウルフラム。2021年5月19日。2021年12月21日時点のオリジナルよりアーカイブ。