Emil Leon Post, Polish-American mathematician and logician (b. 1897)

Emil Leon Post (February 11, 1897 – April 21, 1954) was a brilliant American mathematician and logician whose foundational contributions during the first half of the 20th century profoundly shaped our understanding of computation. Born in Augustów, then part of Congress Poland (Russian Empire), he immigrated to the United States with his family at a young age, embarking on an academic journey that would establish him as a pioneering figure in the field that eventually coalesced into what we now know as computability theory.

Post’s work explored the fundamental limits of what could be computed by algorithms, laying essential groundwork for theoretical computer science and mathematics. He approached these questions with remarkable insight, often independently developing ideas that paralleled, yet distinctively complemented, the research of other giants in the field like Alan Turing and Kurt Gödel. His enduring legacy lies in his rigorous formalizations of computation and his deep investigations into undecidability, which continue to influence modern logic and computing.

Early Life and Academic Journey

Emil Post’s intellectual journey began in New York City, where he attended Townsend Harris High School before excelling at the City College of New York. He pursued his doctoral studies at Columbia University, completing his Ph.D. in mathematics in 1920 under the supervision of Cassius Jackson Keyser. His dissertation, titled "Introduction to a General Theory of Elementary Propositions," already hinted at his profound interest in the logical foundations of mathematics, an area that was then undergoing significant philosophical and technical challenges, particularly in the wake of Bertrand Russell and Alfred North Whitehead's Principia Mathematica.

After receiving his doctorate, Post spent time at Princeton University, engaging with the vibrant mathematical community there, including figures like Alonzo Church. It was during this period, and in the years that followed, that he began to formulate his most original ideas concerning the nature of effective computation and decidability.

Pioneering Contributions to Computability Theory

Emil Post is perhaps best known for his profound and prescient work in computability theory, a branch of mathematical logic that studies which problems can be solved by an algorithm. His contributions were multi-faceted and highly influential:

• Post Production Systems: In 1943, Post introduced the concept of "canonical systems" or "production systems," which were formal systems for manipulating strings of symbols. These systems provided a very general and elegant framework for representing algorithmic processes, serving as a powerful theoretical model of computation. They were highly influential in the development of formal language theory and early programming language design.
• Post Machines: Independently of Alan Turing, Post developed his own formal model of computation, often referred to as a "Post machine" or sometimes a "Post–Turing machine" due to their conceptual similarities. These theoretical machines, which could read and write symbols on an infinite tape following a set of rules, captured the essence of mechanical computation. They demonstrated the equivalence of different models of computation, a crucial step in establishing the Church-Turing thesis.
• The Post Correspondence Problem (PCP): Introduced in 1946, the Post Correspondence Problem is a classic example of an undecidable problem in formal language theory. It asks whether, given a finite list of "dominoes" (pairs of strings), one can find a sequence of dominoes such that the concatenated top strings match the concatenated bottom strings. Proving its undecidability had significant implications for various areas of computer science, including the theory of programming languages and the limits of automated theorem proving.
• Post's Theorem: This theorem establishes a fundamental connection between the arithmetical hierarchy (a classification of sets of natural numbers based on the complexity of their definitions) and the Turing degrees (a classification of the unsolvability of computational problems). It provides a deep insight into the structure of undecidable problems and their relative computational difficulty.

Post's work often tackled the same fundamental questions as Alan Turing (e.g., the Entscheidungsproblem or "decision problem" for first-order logic) and Kurt Gödel (e.g., incompleteness theorems), sometimes arriving at similar conclusions through different conceptual pathways. This independent convergence underscored the robustness and importance of these ideas, cementing his place as a co-founder of modern computability theory.

Later Career and Legacy

Despite his groundbreaking theoretical work, Post faced significant personal challenges, including recurring mental health issues that, at times, interrupted his academic career. Nevertheless, he maintained a faculty position at City College of New York for many years, inspiring students and continuing his research as his health allowed. His publications, though sometimes delayed due to his perfectionism and health, were always deeply insightful and rigorous.

Emil Post passed away prematurely in 1954, but his ideas lived on and flourished. His production systems became foundational for Noam Chomsky's work on formal grammars, which in turn revolutionized linguistics and the design of programming languages. His formal models of computation continue to be taught in computer science and mathematics curricula worldwide, serving as a testament to his profound and lasting impact on our understanding of algorithms, logic, and the very nature of computation.

Frequently Asked Questions About Emil Leon Post

Who was Emil Leon Post?

Emil Leon Post was an American mathematician and logician born in 1897 who made fundamental contributions to mathematical logic and the theory of computation. He is particularly renowned for his work that helped establish the field of computability theory, exploring what can and cannot be computed by algorithms.

What is computability theory?

Computability theory is a branch of mathematical logic that investigates which problems can be solved by an algorithm. It delves into the capabilities and limitations of computational processes, asking questions about decidability (whether an algorithm can always give a 'yes' or 'no' answer) and undecidability (problems for which no such algorithm exists).

What were Emil Post’s most significant contributions to mathematics and computer science?

Post's most significant contributions include the development of Post production systems (a formal system for manipulating strings of symbols that models computation), his independent formulation of a theoretical model of computation similar to Turing machines (sometimes called Post machines), the introduction of the Post Correspondence Problem (PCP) (a classic undecidable problem), and Post's Theorem, which connects the arithmetical hierarchy with Turing degrees.

How does Emil Post’s work relate to Alan Turing’s?

Emil Post and Alan Turing independently developed similar foundational models of computation in the 1930s. Both researchers were addressing the same fundamental questions about the nature of effective calculation and decidability. While Turing’s "Turing machine" is more widely known, Post’s approach, particularly his production systems, offered an equally powerful and influential perspective on the limits of computation, and both contributed to the formulation of the Church-Turing thesis.

What is the Post Correspondence Problem (PCP)?

The Post Correspondence Problem (PCP) is an undecidable decision problem introduced by Emil Post. It involves a finite collection of "dominoes," where each domino has a string of symbols on its top half and another string on its bottom half. The problem asks whether it's possible to find a sequence of these dominoes (allowing repetitions) such that the concatenation of the top strings in the sequence is identical to the concatenation of the bottom strings. Its undecidability means no general algorithm can solve all instances of the PCP.