Post, Emil Leon

Logico e matematico statunitense (Augustów, Polonia, 1897 - New York 1954); prof. (1944) all'univ. di New York. Nel 1921 diede la prima dimostrazione della completezza sintattica del calcolo proposizionale e dell'indecidibilità del calcolo dei predicati; poco dopo introdusse, indipendentemente da L. Wittgenstein, il metodo delle tavole di verità per la logica elementare, proponendo inoltre un sistema formale in cui ciascuna variabile potesse assumere non solo i due valori di verità V e F, ma un valore qualunque tra n valori. Nel 1936 definì il concetto di computabilità e nel 1943 fornì una precisazione della nozione di algoritmo (algoritmo di P.); si occupò inoltre del problema della riducibilità e di problemi di decisione, sviluppando la nozione di gradi di insolubilità. Importante la sua teoria dei sistemi formali e degli insiemi ricorsivamente numerabili, di quegli insiemi, cioè, che o sono vuoti o sono codominî di una funzione ricorsiva. Nel 1947 dimostrò l'impossibilità di risolvere il problema della parola per i semigruppi (v. Thue, Axel: Problema di Thue).