エミール・ポスト

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

Read other articles:

Cordone litorale

Esempio di cordone litorale, Airdrie, Canada Un cordone litorale è una formazione costiera formata dall'azione di trasporto di materiali da parte dei grandi fiumi e dalle correnti della deriva litoranea, che originano depositi che sostituiscono ai contorni della costa, formando una sorta di argine naturale. Un costone è tipicamente costituito da materiali quali sabbia o ciottoli; spesso la formazione ha un andamento ricurvo, soprattutto in prossimità dell'apice, caratteristica probabilment...

 

وزارة النقل (الجزائر)

  لمعانٍ أخرى، طالع وزارة النقل (توضيح).   هذه المقالة عن وزارة النقل والأشغال العمومية. لمعانٍ أخرى، طالع رئيس حكومة الجزائر. وزارة النقل و ن تفاصيل الوكالة الحكومية البلد الجزائر  تأسست 1962 المركز 06 مصطفى خالف بن عكنون، الجزائر،  الجزائر الإدارة الوزراء المس...

 

منتخب السلفادور لاتحاد الرغبي

هذه المقالة تحتاج للمزيد من الوصلات للمقالات الأخرى للمساعدة في ترابط مقالات الموسوعة. فضلًا ساعد في تحسين هذه المقالة بإضافة وصلات إلى المقالات المتعلقة بها الموجودة في النص الحالي. (يوليو 2019) منتخب السلفادور لاتحاد الرغبي بلد الرياضة السلفادور  أكبر فوز أكبر خسارة تع�...

Papa Sergio II

Papa Sergio II102º papa della Chiesa cattolicaElezione25 gennaio 844 Insediamento27 gennaio 844 Fine pontificato27 gennaio 847(3 anni e 2 giorni) Predecessorepapa Gregorio IV Successorepapa Leone IV  NascitaRoma, 790 circa MorteRoma, 27 gennaio 847 SepolturaAntica basilica di San Pietro in Vaticano Manuale Sergio II (Roma, 790 circa – Roma, 27 gennaio 847) è stato il 102º papa della Chiesa cattolica dal gennaio 844 fino alla sua morte. Indice 1 Biografia 1.1 Origini e carr...

 

Geo Bogza

Romanian avant-garde theorist, poet and journalist Geo BogzaBornGheorghe Bogza(1908-02-06)February 6, 1908Blejoi, Prahova County, Kingdom of RomaniaDiedSeptember 14, 1993(1993-09-14) (aged 85)Bucharest, RomaniaOccupationpoet, essayist, journalistNationalityRomanianAlma materNaval AcademyPeriod1928–1993Genrelyric poetry, free verse, prose poetry, reportage, satireLiterary movementAvant-gardeSurrealismSocialist realismRelativesAlexandru Bogza [ro] (father)Radu Tudoran (...

 

Campionato Dilettanti Piemonte-Valle d'Aosta 1958-1959

Voce principale: Campionato Dilettanti 1958-1959. Campionato Nazionale Dilettantifase Piemonte-V. d'A. 1958-1959 Competizione Campionato Nazionale Dilettanti Sport Calcio Edizione 2ª Organizzatore FIGCLega Regionale Piemontese Luogo  Italia Cronologia della competizione 1957-1958 1959-1960 Manuale Il Campionato Nazionale Dilettanti 1958-1959 è stato il V livello del campionato italiano. A carattere regionale, fu il secondo campionato dilettantistico con questo nome, e il settimo se si...

Großsiedlung Siemensstadt

Maeckeritzstrasse Building, Hans Scharoun In der Goebelstraße by Hugo Häring The Siemensstadt Settlement (German: Großsiedlung Siemensstadt; also known as Ring Settlement or Ringsiedlung) is a nonprofit residential community in the Charlottenburg-Wilmersdorf district of Berlin. It is one of the six Modernist Housing Estates in Berlin recognized in July 2008 by UNESCO as a World Heritage Site because of their outstanding modernist architecture and contribution to the progressive housing ref...

 

The World in His Arms

The World in His ArmsPoster film asli karya Reynold BrownSutradaraRaoul WalshProduserAaron RosenbergDitulis olehRex Beach (novel)Borden ChaseHorace McCoy (dialog tambahan)PemeranGregory PeckAnn BlythAnthony QuinnPenata musikFrank SkinnerSinematograferRussell MettyPenyuntingFrank GrossDistributorUniversal-InternationalTanggal rilis 09 Oktober 1952 (1952-10-09) Durasi104 menitNegaraAmerika SerikatBahasaInggrisPendapatankotor$3 juta (rental AS)[1] The World in His Arms adalah ...

 

Rocca Cigliè

Questa voce o sezione sull'argomento centri abitati del Piemonte non cita le fonti necessarie o quelle presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Rocca Cigliècomune Rocca Cigliè – Veduta LocalizzazioneStato Italia Regione Piemonte Provincia Cuneo AmministrazioneSindacoLuigi Ferrua (lista civica) dal 26-5-2014 TerritorioCoordinate44°27′N 7°57′E ...

Battle of Monmouth

American Revolutionary War battle fought on June 28, 1778 For the battle at Monmouth, Wales, see Battle of Monmouth (1233). Battle of MonmouthPart of the Philadelphia campaignWashington Rallying the Troops at Monmouthby Emanuel LeutzeDateJune 28, 1778LocationManalapan Township and Freehold Township, Monmouth, New Jersey40°15′23″N 74°19′15″W / 40.256341°N 74.320899°W / 40.256341; -74.320899Result Inconclusive (see Aftermath)Belligerents  United States &...

 

Starman (film)

1984 film by John Carpenter StarmanTheatrical release posterDirected byJohn CarpenterWritten by Bruce A. Evans Raynold Gideon Produced byLarry J. FrancoStarring Jeff Bridges Karen Allen Charles Martin Smith Richard Jaeckel CinematographyDonald M. MorganEdited byMarion RothmanMusic byJack NitzscheColor processMetrocolorProductioncompaniesIndustrial Light & MagicDelphi II ProductionsDistributed byColumbia PicturesRelease date December 14, 1984 (1984-12-14) Running time115 min...

 

Pemberontakan Tujuh Negara

Pemberontakan Tujuh NegaraPeta yang menunjukkan Pemberontakan Tujuh Negara selama Dinasti HanTanggal154 SMLokasiTiongkok timurHasil Kemenangan HanPihak terlibat Dinasti Han Tujuh Kepangeranan Wu, Chu, Zhao, Jiaoxi, Jiaodong, Zaichuan, dan JinanTokoh dan pemimpin Kaisar Jing dari Han, Zhou Yafu, Dou Ying Liu PiKekuatan 360,000 pasukan 200,000 pasukan Wu 300,000 pasukan dari negara lainKorban Tidak diketahui Seluruh pasukan ditinggalkan, atau ditangkap atau terbunuh Pemberontakan Tujuh Negara a...

Ng Yue Meng

Questa voce sull'argomento nuotatori è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Ng Yue MengNazionalità Singapore Nuoto SpecialitàRana   Modifica dati su Wikidata · Manuale Ng Yue Meng (21 febbraio 1970) è un nuotatore singaporiano, che ha partecipato alle Olimpiadi estive di Seul 1988. Nel torneo olimpico, ha gareggiato nei 100m rana, 200m rana e Staffetta mista 4x100m. Voci cor...

 

Time–frequency analysis

See also: Time–frequency representation In signal processing, time–frequency analysis comprises those techniques that study a signal in both the time and frequency domains simultaneously, using various time–frequency representations. Rather than viewing a 1-dimensional signal (a function, real or complex-valued, whose domain is the real line) and some transform (another function whose domain is the real line, obtained from the original via some transform), time–frequency analysis stud...

 

Ritmo Perfeito

2014 studio album by AnittaRitmo PerfeitoStudio album by AnittaReleased3 June 2014 (2014-06-03)Recorded2014StudioU.M. Music (Rio de Janeiro, Brazil)Genre Pop electropop R&B Length30:55LanguagePortuguese, SpanishProducer Toninho Aguiar Head Media Rafael Castilhol Danilo Sinna Anitta chronology Anitta(2013) Ritmo Perfeito(2014) Meu Lugar(2014) Singles from Ritmo Perfeito CobertorReleased: 24 May 2014 Na BatidaReleased: 29 July 2014 Ritmo PerfeitoReleased: 10 December ...

Agricultural policy

Laws relating to domestic agriculture and foreign-imported agricultural products Agriculture History Prehistory Neolithic Revolution Agriculture in Mesoamerica Austronesian expansion Ancient history Ancient Egypt Ancient Greece Ancient Rome Post-classical Agriculture in the Middle Ages Arab Agricultural Revolution Columbian exchange Modern history British Agricultural Revolution Green Revolution Organic Monoculture On land Agrivoltaic Animal husbandry cattle pigs poultry sheep Dairy Dryland E...

 

江戸前エルフ

江戸前エルフ ジャンル コメディ[1] 漫画 作者 樋口彰彦 出版社 講談社 掲載誌 少年マガジンエッジコミックDAYS レーベル マガジンエッジKC 発表号 少年マガジンエッジ：2019年7月号 - 2023年11月号コミックDAYS：2023年12月20日 - 発表期間 2019年6月17日[2] - 巻数 既刊10巻（2024年9月現在） アニメ 原作 樋口彰彦 監督 安齋剛文 シリーズ構成 ヤスカワショウゴ 脚本 ヤ�...

 

54e régiment d'artillerie

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Cet article présente des problèmes à corriger. Vous pouvez aider à l'améliorer ou bien discuter des problèmes sur sa page de discussion. Son contenu est peut-être sujet à caution et doit absolument être sourcé. Si vous connaissez le sujet traité ici, vous pouvez le retravailler à partir de sources pertinentes en utilisant notamment les notes de bas de page. (Marqué depuis avril 2021) Certaines inform...

G. Cooke Adams

Australian physician and cancer researcher G. Cooke AdamsBorn1865SydneyDied23 June 1934OccupationPhysician George Cooke Adams (1865 – 23 June 1934) was an Australian physician and cancer researcher who proposed the Mulyptol treatment for cancer. Biography Adams was born in Sydney.[1] At age fifteen he worked as a city engineer in Sydney for the Municipal Council for 5 years.[2] He studied medicine at New South Wales College of Pharmacy and obtained his MD from Queen's Univer...

 

アレックス・オチョア

この存命人物の記事には検証可能な出典が不足しています。 信頼できる情報源の提供に協力をお願いします。存命人物に関する出典の無い、もしくは不完全な情報に基づいた論争の材料、特に潜在的に中傷・誹謗・名誉毀損あるいは有害となるものはすぐに除去する必要があります。出典検索?: アレックス・オチョア – ニュース · 書籍 · スカラー&#...