Emil Leon Post

From Free net encyclopedia

(Redirected from Emil Post)

Emil Leon Post (February 11 1897 - April 21 1954) was an American mathematician and logician. He was born in a Polish-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 model, an equally-powerful computer model, which he called Formulation 1. (This model is sometimes called "Post's machine", but is not to be confused with Post's tag machines or other special kinds of Post canonical system, a computational model using string rewriting and developed by Post in 1943).

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

1 Important publications
2 Essential reading
3 See also
4 External links

[edit]

Important publications

E. L. Post, "Finite Combinatory Processes - Formulation 1", Journal of Symbolic Logic, 1, 103-105, 1936.
E. L. Post, "Formal Reductions of the General Combinatorial Decision Problem", American Journal of Mathematics, 65, 197-215, 1943.
E. L. Post, "Recursively enumerable sets of positive integers and their decision problems", Bulletin of the American Mathematical Society, 50, 284-316, 1944. In this article Post introduced the important concept of many-one reduction.

[edit]

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.

[edit]