Emil Leon Post facts for kids
Quick facts for kids
Emil Leon Post
|
|
|---|---|
 |
|
| Born | February 11, 1897 Augustów, Suwałki Governorate, Congress Poland, Russian Empire
(now Poland) |
| Died | April 21, 1954 (aged 57) New York City, U.S.
|
| Alma mater | City College of New York (B.S., 1917) Columbia University (A.M. 1918, Ph.D. 1920) |
| Known for | Formulation 1 Post correspondence problem Completeness-proof of Principia's propositional calculus Post's inversion formula Post's lattice Post's theorem |
| Scientific career | |
| Fields | Mathematics, logic |
| Institutions | Princeton University |
| Thesis | Introduction to a General Theory of Elementary Propositions (1920) |
| Doctoral advisor | Cassius Jackson Keyser |
Emil Leon Post (/poʊst/; February 11, 1897 – April 21, 1954) was an American mathematician and logician. He is famous for his important work in a field now called computability theory. This field explores what can be solved by computers and how.
Contents
Emil Post's Life Story
Emil Post was born in 1897 in a town called Augustów, which was then part of the Russian Empire (and is now in Poland). His family was Polish-Jewish. They moved to New York City in May 1904 when Emil was seven years old. His parents were Arnold and Pearl Post.
Early Challenges and Education
When Emil was twelve, he had a car accident and lost his left arm. Before this, he was very interested in astronomy. However, this injury made it difficult to pursue astronomy as a career. So, he decided to focus on mathematics instead.
Emil went to Townsend Harris High School. After that, he studied at the City College of New York, earning a Bachelor of Science degree in mathematics in 1917. He then continued his studies at Columbia University, where he earned his Ph.D. in mathematics in 1920. His advisor was Cassius Jackson Keyser.
After finishing his Ph.D., Post spent a year doing research at Princeton University (1920–1921). Later, he became a high school mathematics teacher in New York City.
Family Life and Health
In 1929, Emil Post married Gertrude Singer. They had a daughter named Phyllis Post Goodman, who was born in 1932.
Emil faced some health challenges throughout his life. To manage these, he limited his research time to about three hours a day, following his doctor's advice.
In 1936, he joined the mathematics department at the City College of New York. Emil Post passed away in 1954 at the age of 57 from a heart attack.
Emil Post's Early Discoveries
In his Ph.D. paper, published in 1921, Emil Post made some big discoveries. He proved that the logic system in a famous book called Principia Mathematica was "complete." This meant that all true statements (called tautologies) could be proven using the rules and starting points of Principia Mathematica.
Post also came up with truth tables on his own. Truth tables are tools used in logic to figure out if a statement is true or false. Other mathematicians like Charles Sanders Peirce and Ludwig Wittgenstein also developed them around the same time. Post used these tables in a very useful mathematical way.
Almost Discovering Incompleteness
While at Princeton, Post came very close to discovering something called the "incompleteness" of Principia Mathematica. This idea was later proven by Kurt Gödel in 1931. Post didn't publish his ideas at the time because he felt he needed a "complete analysis" for them to be accepted. He later wrote to Gödel in 1938, saying, "I would have discovered Gödel's theorem in 1921—if I had been Gödel."
Contributions to Computability Theory
Emil Post made huge contributions to computability theory. This field studies what problems can be solved by an algorithm or a computer.
Post's Machine and Computation
In 1936, Post created a mathematical model of computation. He did this independently of Alan Turing, who developed a similar model called the Turing machine. Post's model was essentially the same in its power. He called his paper "Formulation 1," planning it to be the first of many models. Sometimes, this model is called "Post's machine" or a Post–Turing machine.
Post also worked on something called a Post canonical system, which uses a method called "string rewriting." This method is now very common in how programming languages are designed and described.
The Post Correspondence Problem
In 1946, Post introduced "correspondence systems" to show simple examples of problems that are "undecidable." This means there's no algorithm that can always solve them. He showed that the Post correspondence problem (PCP) is generally undecidable. The undecidability of this problem became very important for proving other undecidability results in the theory of formal languages.
Post's Problem
In 1944, Post gave an important speech where he asked a big question. He wondered if there was a set of numbers that a computer couldn't fully list, but was also "less complex" than the famous halting problem (another undecidable problem). This question became known as Post's problem. It led to a lot of new research and was finally answered in the 1950s.
Polyadic Groups
In 1940, Post made a very important contribution to the study of polyadic, or n-ary, groups. These are groups where operations can involve more than two elements at a time. His main finding showed how these groups relate to regular groups. He also showed that a polyadic group operation can be described using a regular group operation on the same set of elements.
