Emil Post
Mehr Infos
- Geboren
- Gestorben
- Bekannt für
- Produktionssysteme, das Korrespondenzproblem, Wahrheitstabellen
- Nationalität
- Polnisch-amerikanisch
Der Logiker, der Berechenbarkeit unabhängig von Turing formulierte, im selben Jahr — und in der Wortverbindung „Post-Turing-Maschine" nur zur Fußnote wurde.
Emil Leon Post wurde im damals russischen Augustów geboren und wuchs in New York auf. In seiner Dissertation von 1921 führte er die Wahrheitstabelle als Methode ein und bewies die Vollständigkeit der Aussagenlogik; in unveröffentlichten Notizen aus derselben Zeit näherte er sich zudem etwas, das Gödels Unvollständigkeitssatz nahekommt – ein Jahrzehnt vor Gödels Veröffentlichung. Er legte die Papiere beiseite.
1936 erschien Finite Combinatory Processes — Formulation 1: Ein Arbeiter bewegt sich entlang einer unendlichen Reihe von Kästen und markiert oder entmarkiert sie nach einer Anweisungsliste. Das Modell entspricht praktisch dem Turings, entstanden ohne Kenntnis davon; Post beschrieb es lediglich als einen Menschen, der Befehle befolgt. Es folgten die Produktionssysteme (1943), Grundlage der formalen Grammatiken, und das Postsche Korrespondenzproblem (1946) – unentscheidbar und doch auf einer Serviette formulierbar, daher ein Standardwerkzeug in Unentscheidbarkeitsbeweisen.