Emil Leon Post
1897–1954 · American mathematician and logician
Emil Leon Post (Augustów, 1897 – New York, 1954) was an American mathematician and logician, best known for his work in what came to be called computability theory. Born into a Polish-Jewish family that emigrated to New York City in 1904, he had been drawn to astronomy as a boy. At twelve, however, he lost his left arm in a car accident, which made a career as a professional astronomer unlikely and turned his attention to mathematics.
He graduated from the City College of New York in 1917 and earned his doctorate at Columbia University in 1920. After a year of postdoctoral study at Princeton, he taught high school mathematics in New York. In 1936 he joined the mathematics department of the City College. He suffered from manic episodes and depression, and died in 1954 of a heart attack following electroshock treatment.
In his doctoral work, published in 1921, he proved that the propositional calculus of Principia Mathematica is complete: every tautology is a theorem. He devised truth tables independently of C. S. Peirce and Ludwig Wittgenstein. While at Princeton he came close to discovering the incompleteness of Principia, a result Gödel proved in 1931, though he never published his ideas on the subject.
In 1936, working independently of Alan Turing, he built a model of computation essentially equivalent to the Turing machine, which he called Formulation 1. His canonical systems, based on rewriting strings of symbols, anticipated techniques now common in programming language specification. In 1946 he introduced the Post correspondence problem, a simple example of undecidability that proved central to undecidability results in formal language theory. In 1944 he also posed what became known as Post's problem, asking whether there is a noncomputable recursively enumerable set of Turing degree below that of the halting problem; it was answered affirmatively in the 1950s. In 1940 he made a fundamental contribution to the theory of polyadic, or n-ary, groups.
His influence is felt in computability theory, mathematical logic and theoretical computer science.
Key ideas
- Completeness of propositional logic: every tautology can be proved from the axioms of Principia Mathematica.
- A computational model equivalent to the Turing machine: a rewriting formalism with the same power as the Turing machine, developed independently.
- Post canonical systems: a model of computation based on string rewriting, a precursor of techniques used to specify programming languages.
- The Post correspondence problem: a simple problem whose undecidability serves as a basis for proving undecidability in other fields.
- Post's problem: the question of whether intermediate Turing degrees exist among computably enumerable sets, answered in the 1950s.
Curiosities
An early accident
He lost his left arm at the age of twelve in a car accident, which changed his academic path.
An anticipated idea
In a 1938 postcard to Gödel, he wrote that he would have discovered Gödel's theorem in 1921 if he had been Gödel.
Original Filopedia text based on Wikipedia (es) and Wikipedia (en) and Wikidata.