Emil Post

Emil Leon Post nacque ad Augustów, nell'allora Polonia russa, e crebbe a New York. Nella tesi del 1921 introdusse la tavola di verità come metodo e dimostrò la completezza della logica proposizionale; in appunti inediti dello stesso periodo arrivò anche a qualcosa di simile al teorema di incompletezza di Gödel, dieci anni prima che Gödel pubblicasse il suo. Mise da parte le carte.

Nel 1936 pubblicò Finite Combinatory Processes — Formulation 1: un lavoratore che si sposta tra caselle di una fila infinita, marcandole o smarcandole secondo un elenco di istruzioni. Il modello è in pratica quello di Turing, raggiunto senza conoscerlo; la differenza sta soprattutto nel fatto che Post lo descrisse come un essere umano che esegue ordini. Seguirono i sistemi di produzione (1943), base delle grammatiche formali, e il problema della corrispondenza (1946), indecidibile ma enunciabile su un tovagliolo, e perciò arma standard nelle dimostrazioni di indecidibilità.