# Emil Leon Post

**Emil Leon Post** (February 11 1897 - April 21 1954) was a Polish-American mathematician and logician. He was born in a Jewish family in Augustow, and died in New York City, USA.

In his Columbia University doctoral thesis, he proved, among other things, that the propositional calculus of Principia Mathematica was complete: all tautologies are theorems, given the Principia axioms and a rule of uniform substitution. Van Heijenoort's (1966) source book on mathematical logic reprinted Post's classic article setting out this result. This thesis also devised truth tables independently of Wittgenstein and Charles Peirce and put them to good mathematical use.

In 1936 he developed, independently of Alan Turing's Turing machine, an abstract computer model named the Post machine.

His Post correspondence problem contributed to the decision problems of recursion theory, as a new model of computation.

## Important publications

- E. L. Post, "Recursively enumerable sets of positive integers and their decision problems", Bulletin of the American Mathematical Society
**50**(1944) 284-316

In this article Post introduced the important concept of many-one reduction.

## Essential reading

- Davis, Martin (1993). The Undecidable (Ed.), pp. 288-406. Dover. ISBN 0-486-43228-9. Reprints several papers by Post.
- Davis, Martin (1994). "Emil L. Post: His Life and Work" in Davis, M., ed.,
*Solvability, Provability, Definability: The Collected Works of Emil L. Post*. Birkhäuser: xi--xxviii. A biographical essay.

## See also

## External links

- O'Connor, John J., and Edmund F. Robertson. "Emil Leon Post".
*MacTutor History of Mathematics archive*.

de:Emil Leon Post eo:Emil POST fr:Emil Post pl:Emil Leon Post fa:امیل لئون پست uk:Пост Еміль