Emil-Leon-Post - Emil Leon Post

Emil Leon Post
Emil Leon Post.jpg
Geboren 11. Februar 1897
Augustów , Gouvernement Suwałki , Kongresspolen , Russisches Reich
(jetzt Polen)
Ist gestorben 21. April 1954 (1954-04-21)(57 Jahre)
New York City, USA
Alma Mater City College of New York (BS, 1917)
Columbia University (AM 1918, Ph.D. 1920)
Bekannt für Formulierung 1
Beitrag Korrespondenzproblem
Vollständigkeits-Nachweis der Principia ' s Aussagenlogik
Post Umkehrformel
Gitter der Post
Post - Theorem
Wissenschaftlicher Werdegang
Felder Mathematik , Logik
Institutionen Princeton Universität
These Einführung in eine allgemeine Theorie der Elementarsätze  (1920)
Doktoratsberater Cassius Jackson Keyser

Emil Leon Post ( / p oʊ s t / ; 11. Februar 1897 - 21. April 1954) war ein in Polen geborener US-amerikanischer Mathematiker und Logiker . Er ist vor allem für seine Arbeit auf dem Gebiet bekannt, das schließlich als Berechenbarkeitstheorie bekannt wurde .

Leben

Post wurde in Augustów , Gouvernement Suwałki , Kongresspolen , Russisches Reich (jetzt Polen) in eine polnisch-jüdische Familie geboren, die im Mai 1904 nach New York City einwanderte. Seine Eltern waren Arnold und Pearl Post.

Post hatte sich für Astronomie interessiert, verlor jedoch im Alter von zwölf Jahren bei einem Autounfall seinen linken Arm. Dieser Verlust war ein erhebliches Hindernis, um ein professioneller Astronom zu sein, was zu seiner Entscheidung führte, Mathematik statt Astronomie zu studieren.

Post besuchte die Townsend Harris High School und machte 1917 seinen Bachelor in Mathematik am City College of New York .

Nach Abschluss seines Ph.D. in Mathematik 1920 an der Columbia University , betreut von Cassius Jackson Keyser , promovierte er im akademischen Jahr 1920-1921 an der Princeton University . Post wurde dann Mathematiklehrer an einer High School in New York City.

Post heiratete 1929 Gertrude Singer, mit der er eine Tochter, Phyllis Post Goodman (1932–1995), hatte. Post verbrachte auf Anraten seines Arztes höchstens drei Stunden am Tag mit Forschung, um manische Anfälle zu vermeiden, die er seit seinem Jahr in Princeton erlebt hatte.

1936 wurde er an die Fakultät für Mathematik am City College of New York berufen. Er starb 1954 an einem Herzinfarkt nach einer Elektroschockbehandlung wegen Depressionen ; er war 57.

Frühe Arbeit

In seiner Doktorarbeit, später gekürzt und veröffentlicht als "Introduction to a General Theory of Elementary Propositions" (1921), bewies Post unter anderem, dass die Aussagenkalküle der Principia Mathematica vollständig sind: Alle Tautologien sind Theoreme , angesichts der Principia- Axiome und die Regeln der Substitution und des Modus Ponens . Post hat auch unabhängig von Ludwig Wittgenstein und CS Peirce Wahrheitstabellen entwickelt und mathematisch sinnvoll eingesetzt. Jean van Heijenoorts bekanntes Quellenbuch über mathematische Logik (1966) druckte Posts klassischen Artikel von 1921 über diese Ergebnisse nach.

Während seiner Zeit in Princeton war Post der Entdeckung der Unvollständigkeit von Principia Mathematica sehr nahe , was Kurt Gödel 1931 bewies. Post versäumte es zunächst, seine Ideen zu veröffentlichen, da er glaubte, dass er eine "vollständige Analyse" brauchte, um sie zu akzeptieren. Wie Post 1938 in einer Postkarte an Gödel sagte:

Ich hätte den Satz von Gödel 1921 entdeckt – wenn ich Gödel gewesen wäre.

Rekursionstheorie

1936 entwickelte Post unabhängig von Alan Turing ein mathematisches Berechnungsmodell, das im Wesentlichen dem Turing-Maschinenmodell entsprach . In der Absicht, dies als erstes einer Reihe von Modellen gleicher Leistung, aber zunehmender Komplexität zu betrachten, betitelte er seine Arbeit Formulation 1 . Dieses Modell wird manchmal als "Post-Maschine" oder als Post-Turing-Maschine bezeichnet , ist jedoch nicht mit Posts Tag-Maschinen oder anderen speziellen Arten des kanonischen Systems von Post zu verwechseln , einem Rechenmodell, das String-Rewriting verwendet und von Post in den 1920er Jahren entwickelt wurde, aber zuerst veröffentlicht im Jahr 1943. Posts Rewrite-Technik ist heute in der Spezifikation und dem Design von Programmiersprachen allgegenwärtig, und so ist der Lambda-Kalkül von Church ein hervorstechender Einfluss der klassischen modernen Logik auf das praktische Computing. Post entwickelte eine Methode von "Hilfssymbolen", mit der er jede postgenerative Sprache und tatsächlich jede berechenbare Funktion oder Menge kanonisch darstellen konnte.

Korrespondenzsysteme wurden 1946 von der Post eingeführt, um einfache Beispiele für Unentscheidbarkeit zu geben. Er zeigte, dass das Postkorrespondenzproblem (PCP) der Erfüllung ihrer Beschränkungen im Allgemeinen unentscheidbar ist. Die Unentscheidbarkeit seines Post-Korrespondenzproblems erwies sich als genau das, was man brauchte, um Unentscheidbarkeitsergebnisse in der Theorie der formalen Sprachen zu erhalten .

In einer einflussreichen Ansprache vor der American Mathematical Society im Jahr 1944 stellte er die Frage nach der Existenz einer unberechenbaren rekursiv aufzählbaren Menge, deren Turing-Grad geringer ist als der des Halteproblems . Diese Frage, die als Post-Problem bekannt wurde , regte viele Forschungen an. Sie wurde in den 1950er Jahren durch die Einführung der mächtigen Prioritätsmethode in der Rekursionstheorie bejaht .

Polyadische Gruppen

Post hat in einem 1940 veröffentlichten langen Artikel einen grundlegenden und immer noch einflussreichen Beitrag zur Theorie der polyadischen oder n- ären Gruppen geleistet . Sein Hauptsatz zeigte, dass eine polyadische Gruppe die iterierte Multiplikation von Elementen einer normalen Untergruppe einer Gruppe ist , so dass die Quotientengruppe zyklisch der Ordnung n − 1 ist. Er zeigte auch, dass eine polyadische Gruppenoperation auf einer Menge durch eine Gruppenoperation auf derselben Menge ausgedrückt werden kann. Das Papier enthält viele weitere wichtige Ergebnisse.

Ausgewählte Papiere

  • Post, Emil Leon (1919). "Die verallgemeinerten Gammafunktionen" . Annalen der Mathematik . Zweite Serie. 20 (3): 202–217. doi : 10.2307/1967871 . JSTOR  1967871 .
  • Post, Emil Leon (1921). „Einführung in eine allgemeine Theorie der Elementarsätze“. Amerikanische Zeitschrift für Mathematik . 43 (3): 163–185. doi : 10.2307/2370324 . hdl : 2027/uiuo.ark:/13960/t9j450f7q . JSTOR  2370324 .
  • Post, Emil Leon (1936). „Finite Kombinatorische Prozesse – Formulierung 1“. Zeitschrift für symbolische Logik . 1 (3): 103–105. doi : 10.2307/2269031 . JSTOR  2269031 .
  • Post, Emil Leon (1940). "Polyadische Gruppen" . Transaktionen der American Mathematical Society . 48 (2): 208–350. doi : 10.2307/1990085 . JSTOR  1990085 .
  • Post, Emil Leon (1943). „Formale Reduktionen des allgemeinen kombinatorischen Entscheidungsproblems“. Amerikanische Zeitschrift für Mathematik . 65 (2): 197–215. doi : 10.2307/2371809 . JSTOR  2371809 .
  • Post, Emil Leon (1944). "Rekursiv aufzählbare Mengen von positiven ganzen Zahlen und ihre Entscheidungsprobleme" . Bulletin der American Mathematical Society . 50 (5): 284–316. doi : 10.1090/s0002-9904-1944-08111-1 .Führt das wichtige Konzept der Viele-Eins-Reduktion ein .

Siehe auch

Anmerkungen

Verweise

Weiterlesen

  • Anshel, Iris Lee; Anshel, Michael (November 1993). „Vom Post-Markov-Theorem durch Entscheidungsprobleme zur Public-Key-Kryptographie“. The American Mathematical Monthly . Mathematische Vereinigung von Amerika. 100 (9): 835–844. doi : 10.2307/2324657 . JSTOR  2324657 .
    Emil Post gewidmet und enthält spezielles Material zur Post. Dazu gehört "Post's Relation to the Cryptology and Cryptographists of his Era: ... Steven Brams, der bekannte Spieltheoretiker und Politikwissenschaftler, hat uns gegenüber bemerkt, dass das Leben und Vermächtnis von Emil Post einen Aspekt des New Yorker intellektuellen Lebens während der der ersten Hälfte des zwanzigsten Jahrhunderts, die einer tieferen Erforschung dringend bedarf. Die Autoren hoffen, dass dieser Aufsatz dazu dient, dieses Streben zu fördern". (S. 842–843)
  • Davis, Martin, Hrsg. (1993). Das Unentscheidbare . Dover. S.  288 –406. ISBN 0-486-43228-9.
    Reprints mehrere Papiere 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 biografischer Essay.
  • Jackson, Allyn (Mai 2008). „Ein Interview mit Martin Davis“ . Hinweise des AMS . 55 (5): 560–571.
    Viel Material zu Emil Post aus seinen Erinnerungen aus erster Hand.

Externe Links