Emil Leon Post
Encyclopedia
Emil Leon Post was a mathematician
and logician. He is best known for his work in the field that eventually became known as computability theory
.
when he was a child. After completing his Ph.D.
in mathematics at Columbia University
, he did a post-doctorate at Princeton University
. While at Princeton, he came very close to discovering the incompleteness of Principia Mathematica
, which Kurt 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 the City College of New York
, where he remained until his death, in 1954, from a heart attack
at the age of 57.
In his doctoral thesis, Post proved, among other things, that the propositional calculus of Principia Mathematica was complete: all tautologies
are theorem
s, given the Principia axioms and the rules of substitution and modus ponens
. Post also devised truth tables independently of Wittgenstein and C.S. Peirce and put them to good mathematical use. Jean Van Heijenoort
's well-known source book on mathematical logic (1966) reprinted Post's classic article setting out these results.
, 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 paper Formulation 1. This model is sometimes called "Post's machine" or a Post-Turing 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 the 1920s but first published in 1943. Post's rewrite technique is now ubiquitous in programming language specification and design, and so with Church's lambda-calculus is a salient influence of classical modern logic on practical computing. Post devised a method of 'auxiliary symbols' by which he could canonically represent any Post-generative language, and indeed any computable function or set at all.
The unsolvability of his Post correspondence problem
turned out to be exactly what was needed to obtain unsolvability results in the theory of formal languages.
In an influential address to the American Mathematical Society
in 1944, he raised the question of the existence of an uncomputable recursively enumerable set whose Turing degree
is less than that of the halting 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 in recursion theory
.
in a long paper published in 1940. His major theorem showed that a polyadic group is the iterated multiplication of elements of a normal subgroup of a group, such that the quotient group is cyclic of order n − 1. He also demonstrated that a polyadic group operation on a set can be expressed in terms of a group operation on the same set. The paper contains many other important results.
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
and logician. He is best known for his work in the field that eventually became known as computability theory
Computability theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
.
Early work
Post was born into a Polish-Jewish family that immigrated to AmericaUnited States
The United States of America is a federal constitutional republic comprising fifty states and a federal district...
when he was a child. After completing his Ph.D.
Doctor of Philosophy
Doctor of Philosophy, abbreviated as Ph.D., PhD, D.Phil., or DPhil , in English-speaking countries, is a postgraduate academic degree awarded by universities...
in mathematics at Columbia University
Columbia University
Columbia University in the City of New York is a private, Ivy League university in Manhattan, New York City. Columbia is the oldest institution of higher learning in the state of New York, the fifth oldest in the United States, and one of the country's nine Colonial Colleges founded before the...
, he did a post-doctorate at Princeton University
Princeton University
Princeton University is a private research university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League, and is one of the nine Colonial Colleges founded before the American Revolution....
. While at Princeton, he came very close to discovering the incompleteness of Principia Mathematica
Principia Mathematica
The Principia Mathematica is a three-volume work on the foundations of mathematics, written by Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913...
, which Kurt Gödel
Kurt Gödel
Kurt Friedrich Gödel was an Austrian logician, mathematician and philosopher. Later in his life he emigrated to the United States to escape the effects of World War II. One of the most significant logicians of all time, Gödel made an immense impact upon scientific and philosophical thinking in the...
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 the City College of New York
City College of New York
The City College of the City University of New York is a senior college of the City University of New York , in New York City. It is also the oldest of the City University's twenty-three institutions of higher learning...
, where he remained until his death, in 1954, from a heart attack
Myocardial infarction
Myocardial infarction or acute myocardial infarction , commonly known as a heart attack, results from the interruption of blood supply to a part of the heart, causing heart cells to die...
at the age of 57.
In his doctoral thesis, Post proved, among other things, that the propositional calculus of Principia Mathematica was complete: all tautologies
Tautology (logic)
In logic, a tautology is a formula which is true in every possible interpretation. Philosopher Ludwig Wittgenstein first applied the term to redundancies of propositional logic in 1921; it had been used earlier to refer to rhetorical tautologies, and continues to be used in that alternate sense...
are theorem
Theorem
In mathematics, a theorem is a statement that has been proven on the basis of previously established statements, such as other theorems, and previously accepted statements, such as axioms...
s, given the Principia axioms and the rules of substitution and modus ponens
Modus ponens
In classical logic, modus ponendo ponens or implication elimination is a valid, simple argument form. It is related to another valid form of argument, modus tollens. Both Modus Ponens and Modus Tollens can be mistakenly used when proving arguments...
. Post also devised truth tables independently of Wittgenstein and C.S. Peirce and put them to good mathematical use. Jean Van Heijenoort
Jean Van Heijenoort
Jean Louis Maxime van Heijenoort was a pioneer historian of mathematical logic. He was also a personal secretary to Leon Trotsky from 1932 to 1939, and from then until 1947, an American Trotskyist activist.-Life:Van Heijenoort was born in Creil, France...
's well-known source book on mathematical logic (1966) reprinted Post's classic article setting out these results.
Recursion theory
In 1936, Post developed, independently of Alan TuringAlan Turing
Alan Mathison Turing, OBE, FRS , was an English mathematician, logician, cryptanalyst, and computer scientist. He was highly influential in the development of computer science, providing a formalisation of the concepts of "algorithm" and "computation" with the Turing machine, which played a...
, a mathematical model of computation that was essentially equivalent to the Turing machine model
Turing
Alan Turing was a British mathematician, logician, cryptanalyst, and computer scientist.Turing may also refer to:*Turing machine, a basic, abstract symbol-manipulating device...
. Intending this as the first of a series of models of equivalent power but increasing complexity, he titled his paper Formulation 1. This model is sometimes called "Post's machine" or a Post-Turing machine
Post-Turing machine
A Post–Turing machine is a "program formulation" of an especially simple type of Turing machine, comprising a variant of Emil Post's Turing-equivalent model of computation described below. A Post–Turing machine is a "program formulation" of an especially simple type of Turing machine, comprising a...
, but is not to be confused with Post's tag machines
Tag system
A tag system is a deterministic computational model published by Emil Leon Post in 1943 as a simple form of Post canonical system. A tag system may also be viewed as an abstract machine, called a Post tag machine —briefly, a finite state machine whose only tape is a FIFO queue of unbounded length,...
or other special kinds of Post canonical system
Post canonical system
A Post canonical system, as created by Emil Post, is a string-manipulation system that starts with finitely-many strings and repeatedly transforms them by applying a finite set of specified rules of a certain form, thus generating a formal language...
, a computational model using string rewriting and developed by Post in the 1920s but first published in 1943. Post's rewrite technique is now ubiquitous in programming language specification and design, and so with Church's lambda-calculus is a salient influence of classical modern logic on practical computing. Post devised a method of 'auxiliary symbols' by which he could canonically represent any Post-generative language, and indeed any computable function or set at all.
The unsolvability of his Post correspondence problem
Post correspondence problem
The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. Because it is simpler than the halting problem and the Entscheidungsproblem it is often used in proofs of undecidability....
turned out to be exactly what was needed to obtain unsolvability results in the theory of formal languages.
In an influential address to the American Mathematical Society
American Mathematical Society
The American Mathematical Society is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, which it does with various publications and conferences as well as annual monetary awards and prizes to mathematicians.The society is one of the...
in 1944, he raised the question of the existence of an uncomputable recursively enumerable set whose Turing degree
Turing degree
In computer science and mathematical logic the Turing degree or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set...
is less than that of the halting problem
Halting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
. 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 in recursion theory
Recursion theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
.
Polyadic groups
Post made a fundamental and still influential contribution to the theory of polyadic, or n-ary, groupsN-ary group
In mathematics, an n-ary group is a generalization of a group to a set G with a n-ary operation instead of a binary operation. The axioms for an n-ary group are defined in such a way as to reduce to those of a group in the case .-Associativity:The easiest axiom to generalize is the associative law...
in a long paper published in 1940. His major theorem showed that a polyadic group is the iterated multiplication of elements of a normal subgroup of a group, such that the quotient group is cyclic of order n − 1. He also demonstrated that a polyadic group operation on a set can be expressed in terms of a group operation on the same set. The paper contains many other important results.
Selected papers
- 1936, "Finite Combinatory Processes - Formulation 1," Journal of Symbolic Logic 1: 103–105.
- 1940, "Polyadic groups", Transactions of the American Mathematical Society 48: 208–350.
- 1943, "Formal Reductions of the General Combinatorial Decision Problem," American Journal of MathematicsAmerican Journal of MathematicsThe American Journal of Mathematics is a bimonthly mathematics journal published by the Johns Hopkins University Press.- History :The American Journal of Mathematics is the oldest continuously-published mathematical journal in the United States, established in 1878 at the Johns Hopkins University...
65: 197–215. - 1944, "Recursively enumerable sets of positive integers and their decision problems," Bulletin of the American Mathematical SocietyBulletin of the American Mathematical SocietyThe Bulletin of the American Mathematical Society is a quarterly mathematical journal published by the American Mathematical Society...
50: 284–316. Introduces the important concept of many-one reductionMany-one reductionIn computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem. Reductions are thus used to measure the relative computational difficulty of two problems.Many-one...
.
See also
- Post's problem
- Post's theoremPost's theoremIn computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees.- Background :The statement of Post's theorem uses several concepts relating to definability and recursion theory...
- Post's inversion formulaPost's inversion formulaPost's inversion formula for Laplace transforms, named after Emil Post, is a simple-looking but usually impractical formula for evaluating an inverse Laplace transform....
- Arithmetical hierarchyArithmetical hierarchyIn mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene-Mostowski hierarchy classifies certain sets based on the complexity of formulas that define them...
- Post's lattice
- Functional completeness
- List of multiple discoveries
Further reading
- Anshel, Iris Lee; Anshel, Michael, "From the Post-Markov Theorem Through Decision Problems to Public-Key Cryptography", The American Mathematical Monthly, Vol. 100, No. 9 (Nov., 1993), pp. 835–844, Mathematical Association of America. Dedicated to Emil Post and contains special material on Post. This includes "Post's Relation to the Cryptology and Cryptographists of his Era: ... Steven Brams, the noted game theorist and political scientist, has remarked to us that the life and legacy of Emil Post represents one aspect of New York intellectual life during the first half of the twentieth century that is very much in need of deeper exploration. The authors hope that this paper serves to further this pursuit". (pp. 842–3)
External links
- http://www.ams.org/notices/200805/An interview with Martin DavisMartin DavisMartin David Davis, is an American mathematician, known for his work on Hilbert's tenth problem . He received his Ph.D. from Princeton University in 1950, where his adviser was Alonzo Church . He is Professor Emeritus at New York University. He is the co-inventor of the Davis-Putnam and the DPLL...
] - Notices of the AMS, May 2008. Much material on Emil Post from his first-hand recollections. - Emil Post biographical article by Alasdair UrquhartAlasdair UrquhartAlasdair Ian Fenton Urquhart, born December 20, 1945, is an emeritus Professor of Philosophy at the University of Toronto. He has made notable contributions to the field of logic, especially non-classical logic. One of his most notable achievements is proving the undecidability of the relevance...
.