Emil Leon Post ( / p oʊ st / ; 11. Februar 1897 – 21. April 1954) war ein US-amerikanischer Mathematiker und Logiker . Er ist vor allem für seine Arbeiten auf dem Gebiet bekannt, das später als Berechenbarkeitstheorie bekannt wurde .

Leben

Post wurde in Augustów , Gouvernement Suwałki , Kongresspolen , Russisches Kaiserreich (heute Polen), in eine polnisch-jüdische Familie geboren, die im Mai 1904 nach New York City eingewandert war. Seine Eltern waren Arnold und Pearl Post. [ 2 ]

Post hatte sich für Astronomie interessiert, verlor aber im Alter von zwölf Jahren bei einem Autounfall seinen linken Arm. Dieser Verlust stellte ein erhebliches Hindernis für eine Karriere als professioneller Astronom dar und führte zu seiner Entscheidung, Mathematik statt Astronomie zu studieren. [ 3 ]

Post besuchte die Townsend Harris High School und schloss 1917 sein Studium am City College of New York mit einem Bachelor of Science in Mathematik ab. [ 1 ]

Nach seiner Promotion in Mathematik im Jahr 1920 an der Columbia University unter der Betreuung von Cassius Jackson Keyser absolvierte er im akademischen Jahr 1920/21 ein Postdoktorat an der Princeton University . Anschließend wurde Post Mathematiklehrer an einer High School in New York City.

Post heiratete 1929 Gertrude Singer (1900–1956), mit der er eine Tochter, Phyllis Post Goodman (1932–1995), hatte. [ 4 ] Auf Anraten seines Arztes widmete Post maximal drei Stunden täglich der Forschung, um manische Schübe zu vermeiden, unter denen er seit seinem Jahr in Princeton litt. [ 5 ]

1936 wurde er an die Mathematikfakultät des City College of New York berufen. Er starb im April 1954 an einem Herzinfarkt infolge einer Elektroschocktherapie gegen Depressionen . [ 5 ] [ 6 ]

Frühe Arbeiten

In seiner später gekürzten und unter dem Titel „Einführung in eine allgemeine Theorie der elementaren Aussagen“ (1921) veröffentlichten Dissertation bewies Post unter anderem die Vollständigkeit des Aussagenkalküls der Principia Mathematica : Alle Tautologien sind Theoreme , gegeben die Axiome der Principia sowie die Regeln der Substitution und des Modus ponens . Unabhängig von C. S. Peirce und Ludwig Wittgenstein entwickelte Post zudem Wahrheitstabellen und nutzte diese in der Mathematik. Jean van Heijenoorts bekanntes Standardwerk zur mathematischen Logik (1966) enthielt einen Nachdruck von Posts klassischem Artikel aus dem Jahr 1921, in dem er diese Ergebnisse darlegte.

Während seiner Zeit in Princeton kam Post der Entdeckung der Unvollständigkeit der Principia Mathematica , die Kurt Gödel 1931 bewies, sehr nahe. Post veröffentlichte seine Ideen zunächst nicht, da er glaubte, für deren Akzeptanz eine „vollständige Analysis“ zu benötigen. [ 2 ] Wie Post 1938 in einer Postkarte an Gödel schrieb:

Ich hätte Gödels Theorem im Jahr 1921 entdeckt – wenn ich Gödel gewesen wäre. [ 7 ]

Rekursionstheorie

1936 entwickelte Post unabhängig von Alan Turing ein mathematisches Berechnungsmodell, das im Wesentlichen dem Turingmaschinenmodell entsprach . Er beabsichtigte, dies als erstes einer Reihe von Modellen mit vergleichbarer Leistungsfähigkeit, aber zunehmender Komplexität zu betrachten und gab seiner Arbeit den Titel „ Formulierung 1“ . Dieses Modell wird mitunter als „Post-Maschine“ oder Post-Turing-Maschine bezeichnet, ist aber nicht mit Posts Tag-Maschinen oder anderen speziellen Arten des Post-kanonischen Systems zu verwechseln . Letzteres ist ein Berechnungsmodell, das auf String-Umschreibung basiert und von Post in den 1920er Jahren entwickelt, aber erst 1943 veröffentlicht wurde. Posts Umschreibungstechnik ist heute in der Spezifikation und im Entwurf von Programmiersprachen allgegenwärtig, und ebenso wie Churchs Lambda-Kalkül stellt sie einen prägenden Einfluss der klassischen modernen Logik auf die praktische Informatik dar. Post entwickelte eine Methode von „Hilfssymbolen“, mit der er jede Post-generative Sprache und tatsächlich jede berechenbare Funktion oder Menge kanonisch darstellen konnte .

Korrespondenzsysteme wurden 1946 von Post eingeführt, um einfache Beispiele für Unentscheidbarkeit zu liefern . [ 8 ] Er zeigte, dass das Post-Korrespondenzproblem (PCP) zur Erfüllung ihrer Nebenbedingungen im Allgemeinen unentscheidbar ist. Die Unentscheidbarkeit des Korrespondenzproblems erwies sich als genau das, was benötigt wurde, um Unentscheidbarkeitsresultate in der Theorie formaler Sprachen zu erzielen .

In einer einflussreichen Rede vor der American Mathematical Society im Jahr 1944 warf er die Frage nach der Existenz einer nicht berechenbaren, rekursiv aufzählbaren Menge auf , deren Turinggrad kleiner ist als der des Halteproblems . Diese Frage, die als Posts Problem bekannt wurde , regte umfangreiche Forschungen an. Sie wurde in den 1950er Jahren durch die Einführung der leistungsstarken Prioritätsmethode in der Berechenbarkeitstheorie bejaht .

Polyadische Gruppen

Post leistete mit einer 1940 veröffentlichten umfangreichen Arbeit einen grundlegenden und bis heute einflussreichen Beitrag zur Theorie der polyadischen ( n -ären) Gruppen . Sein Hauptsatz zeigte, dass eine polyadische Gruppe das iterierte Produkt von Elementen eines Normalteilers einer Gruppe ist , sodass die Quotientengruppe zyklisch von Ordnung n − 1 ist . Er bewies außerdem, dass eine polyadische Gruppenoperation auf einer Menge durch eine Gruppenoperation auf derselben Menge ausgedrückt werden kann. Die Arbeit enthält viele weitere wichtige Ergebnisse.

Ausgewählte Aufsätze

Siehe auch

Anmerkungen

  1. ^ a b Urquhart (2008)
  2. ^ a b c O'Connor, John J.; Robertson, Edmund F. , "Emil Leon Post" , MacTutor History of Mathematics Archive , University of St Andrews
  3. ^ Urquhart 2008 , S. 429.
  4. ^ „Phyllis Post Goodman Park“ . NYC Parks .
  5. ^ a b Urquhart (2008), S. 430.
  6. ^ Baaz, Matthias (Hrsg.). (2011). Kurt Gödel und die Grundlagen der Mathematik: Horizonte der Wahrheit (1. Aufl.). Cambridge University Press. ISBN 9781139498432Die
  7. ^ Stillwell, John (2004). „Emil Post und seine Vorwegnahme von Gödel und Turing“ . Mathematics Magazine . 77 (1): 3–14 . doi : 10.2307/3219226 . ISSN 0025-570X . JSTOR 3219226 .  
  8. ^ EL Post (1946). „Eine Variante eines rekursiv unlösbaren Problems“ (PDF) . Bull. Amer. Math. Soc. 52 (4): 264–269 . doi : 10.1090/s0002-9904-1946-08555-9 .

Referenzen

Weiterführende Literatur

  • Anshel, Iris Lee; Anshel, Michael (November 1993). „Vom Post-Markov-Theorem über Entscheidungsprobleme zur Public-Key-Kryptographie“. The American Mathematical Monthly . 100 (9). Mathematical Association of America: 835–844 . doi : 10.2307/2324657 . JSTOR  2324657 .
    Diese Arbeit ist Emil Post gewidmet und enthält spezielles Material über ihn. Darin heißt es unter anderem: „Posts Verhältnis zur Kryptologie und den Kryptographen seiner Zeit: … Steven Brams, der bekannte Spieltheoretiker und Politikwissenschaftler, hat uns gegenüber angemerkt, dass Leben und Werk von Emil Post einen Aspekt des New Yorker Geisteslebens in der ersten Hälfte des 20. Jahrhunderts darstellen, der einer eingehenderen Erforschung bedarf. Die Autoren hoffen, dass diese Arbeit dazu beiträgt, diese Forschung voranzutreiben.“ (S. 842–843)
  • Davis, Martin (Hrsg.). (1993). Das Unentscheidbare . Dover. S.  288–406 . ISBN 0-486-43228-9Die
    Enthält Nachdrucke mehrerer Artikel von Post.
  • Davis, Martin (1994). „Emil L. Post: Sein Leben und Werk“. Lösbarkeit, Beweisbarkeit, Definierbarkeit: Die gesammelten Werke von Emil L. Post . Birkhäuser. S.  xi– xxviii.
    Ein biographischer Essay.
  • Jackson, Allyn (Mai 2008). „Ein Interview mit Martin Davis“ . Notices of the AMS . 55 (5): 560–571 .
    Viel Material über Emil Post aus seinen eigenen Erinnerungen.
  • Jackson, Allyn (Oktober 2018). „Emil Post: Psychologische Treue“ . Inference: International Review of Science . doi : 10.37282/991819.18.48 . S2CID  240012225 .
    Ein biographischer Artikel.