- Emil Leon Post
Infobox_Scientist
name = Emil Leon Post
image_width =
birth_date =February 11 ,1897
birth_place =Augustów , thenRussian Empire
death_date =April 21 1954 ,
death_place =New York City , flagicon|USA U.S.
residence =
nationality =
field =Mathematics
work_institution =
alma_mater =Columbia University
doctoral_advisor =
doctoral_students =
known_for = Formulation 1,
Post correspondence problem ,
completeness-proof of Principia's propositional calculus
prizes =
religion =
footnotes =Emil Leon Post,
Ph.D. , (February 11 1897 ,Augustów –April 21 1954 ,New York City ) was amathematician andlogician .Early work
Post was born into a Polish-Jewish family that immigrated to America when he was a child. After completing his Ph.D. in mathematics at
Columbia University , he did a post doctorate atPrinceton University . While at Princeton, he came very close to discovering the incompleteness of "Principia Mathematica ", whichKurt Gödel proved in 1931. Post then became a high school mathematics teacher in New York City. In 1936, he was appointed to the mathematics department at theCity College of the College of the City of New York, where he remained until his death.In his
Columbia University doctoral thesis, Post proved, among other things, that the propositional calculus of "Principia Mathematica" was complete: all tautologies aretheorem s, given the "Principia" axioms and the rules of substitution andmodus ponens . Post also devised truth tables independently ofWittgenstein andCharles Peirce and put them to good mathematical use.Jean Van Heijenoort 's (1966) well-known source book on mathematical logic reprinted Post's classic article setting out these results.Recursion theory
In 1936. Post developed, independently of
Alan Turing , a mathematical model of computation that was essentially equivalent to the Turing machine model. Intending this as the first of a series of models of equivalent power but increasing complexity, he titled his paperFormulation 1 . (This model is sometimes called "Post's machine" or aPost-Turing machine , but is not to be confused with Post's tag machines or other special kinds of Post canonical system, a computational model usingstring rewriting and developed by Post in the 1920s but first published in 1943).The unsolvability of his
Post correspondence problem turned out to be exactly what was needed to obtain unsolvability results in the theory offormal languages .In an influential address to the
American Mathematical Society in 1944, he raised the question of the existence of an uncomputablerecursively enumerable set whoseTuring degree is less than that of thehalting problem . This question, which became known as Post's Problem, stimulated much research. It was solved in the affirmative in the 1950s by the introduction of the powerful priority method inrecursion theory .elected papers
* 1936, "Finite Combinatory Processes - Formulation 1," "Journal of Symbolic Logic 1": 103-105.
* 1943, "Formal Reductions of the General Combinatorial Decision Problem," "American Journal of Mathematics 65": 197-215.
* 1944, "Recursively enumerable sets of positive integers and their decision problems," "Bulletin of the American Mathematical Society 50": 284-316. Introduces the important concept ofmany-one reduction .Essential reading
* [http://www.amphilsoc.org/library/mole/p/post.htm Emil Leon Post Papers 1888-1995] -
American Philosophical Society , Philadelphia, Pennsylvania.
*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.ee also
*
Post's problem
*Post's theorem
*Post's inversion formula
*Arithmetical hierarchy
*Post's lattice External links
*MacTutor Biography|id=Post
*
* [http://www.ams.org/notices/200805/ An interview withMartin Davis ] - Notices of the AMS, May 2008. Much material on Emil Post from his first-hand recollections.
Wikimedia Foundation. 2010.