Emil Post

Emil Leon Post werd geboren in Augustów, destijds Russisch Polen, en groeide op in New York. In zijn proefschrift uit 1921 voerde hij de waarheidstabel in als methode en bewees hij de volledigheid van de propositielogica; in niet-gepubliceerde aantekeningen uit dezelfde tijd kwam hij ook uit bij iets wat lijkt op Gödels onvolledigheidsstelling, een decennium voordat Gödel de zijne publiceerde. Hij legde de papieren weg.

In 1936 publiceerde hij Finite Combinatory Processes — Formulation 1: een werker die zich langs vakjes in een oneindige rij beweegt en ze markeert of de markering weghaalt volgens een lijst instructies. Het model is in feite dat van Turing, bereikt zonder kennis ervan; het verschilt vooral doordat Post het beschreef als een mens die bevelen opvolgt. Daarna kwamen de productiesystemen (1943), de basis van formele grammatica's, en het correspondentieprobleem (1946) — een onbeslisbaar probleem dat simpel genoeg is om op een servet te formuleren en daardoor een standaardwapen in onbeslisbaarheidsbewijzen.