Emil Leon Post

Post, Emil Leon 

Born Feb. 11, 1897, in Augustów, Poland; died Apr. 21, 1954, in New York. American mathematician and logician.

Post, who lectured on mathematics and logic at Columbia University, New York University, and other American universities, obtained several fundamental results in mathematical logic. He gave one of the most useful definitions of the concepts of consistency and completeness of formal systems (calculi) and proved the functional completeness and deductive completeness (in the broad and narrow sense) of the propositional calculus. He also studied systems of many-valued logic with more than three truth values. Post was one of the first to define an algorithm— independently of A. M. Turing—as an abstract computing machine; he formulated the basic thesis of the theory of algorithms, according to which it is possible to describe any algorithm by means of this definition. He also obtained results on the expressibility of general recursive functions and predicates; in particular, he derived what is now known as the normal form theorem. He and A. A. Markov were the first to prove that a number of problems in mathematical logic and algebra were algorithmically unsolvable.

REFERENCE

Kleene, S. C. Vvedenie ν metamatematiku. Moscow, 1957. (Translated from English; with bibliography.)