Celebrating Emil Post & His "Intractable Problem" of Tag: 100 Years Later
Wolfram・2 minutes read
Emil Post, a mathematician born in 1897, explored the problem of tag and computational irreducibility, leading to significant contributions to mathematical logic and universal computation despite facing mental health struggles. Post's work on tag systems and transformation rules showcased the complexity and unpredictability of computations, underscoring the challenges posed by computational irreducibility in understanding mathematical systems and the universe as a whole.
Insights
- Emil Post was a mathematician born in 1897 who delved into fundamental questions about mathematics, particularly focusing on string rewriting operations and the problem of tag.
- Post's exploration of the problem of tag revealed its complexity and unpredictability, with some cases requiring thousands of steps to terminate, leading to a sense of hopelessness in solving finiteness problems.
- Post's work introduced computational irreducibility and the concept of universal computation through simple rules leading to complex behavior, challenging the need for complex constructions for universality.
- Post's meticulous nature and dedication to intellectual pursuits are reflected in his strict daily schedule, diverse interests, and commitment to education, culminating in a scholarship established in his name at City College.
- Post's academic journey, from Brooklyn College to City College, involved delving into various mathematical topics, including writing about Jesse Douglas and astronomy, showcasing his broad interests and academic pursuits.
- The ongoing efforts to solve Post's tag system problem, with extensive computational analyses and collaborations with Charity Engine and Stephen Wolfram, highlight the concept of computational irreducibility and the enduring challenges in computational history.
Get key ideas from YouTube videos. It’s free
Recent questions
What was Emil Post's central question in mathematics?
Emil Post's central question in mathematics revolved around determining the equality of two mathematical expressions through sequences of string rewritings. He aimed to simplify complex mathematical expressions to string rewriting operations, focusing on the underlying primitives of mathematics beyond basic logic operations. Post's work predated the existence of computers and Turing machines, emphasizing the importance of understanding fundamental questions about mathematics.
How did Emil Post contribute to computational universality?
Emil Post's work on the problem of tag delved into the concept of computational universality, where simple rules can lead to complex behavior. By identifying a specific class of string rewritings and exploring the normal form, Post showcased how transformation rules, as seen in tag systems, extend beyond mathematics to represent computations in various fields. His observations challenged the notion that complex constructions were necessary for achieving universality, highlighting the significance of string transformations in computation.
What was the significance of Emil Post's work on computational irreducibility?
Emil Post's exploration of computational irreducibility in a specific tag system raised questions about its depth and potential implications. By deriving computation from basic principles and observing computational irreducibility, Post contributed to understanding the limitations and complexities involved in computational processes. His work paved the way for further developments in mathematical logic, including Godel's theorem and Alonzo Church's lambda calculus, emphasizing the enduring nature of computational challenges in history.
How did Emil Post's personal struggles impact his career in mathematics?
Emil Post's bipolar disorder, managed through a strict schedule, significantly impacted his career in mathematics. His mental health issues led to hospitalizations and periods of absence, affecting his research and teaching responsibilities. Post's commitment to education and academic excellence remained evident despite his personal struggles, reflecting his dedication to intellectual pursuits and overcoming challenges. His meticulous timekeeping and habits, including strict schedules and academic achievements, showcased his resilience in the face of adversity.
What was the goal of Emil Post's academic journey?
Emil Post's academic journey aimed to formalize all existing mathematics, seeking a single algorithm for the entire field. He developed a general form of symbolic logic using combinatory iteration, focusing on simplifying complex mathematical expressions to reveal the core problem. Post's emphasis on finite processes over computability led to systems more relevant to computing and programming, highlighting his dedication to understanding fundamental questions about mathematics beyond basic logic operations.
Related videos
Veritasium
Math's Fundamental Flaw
Quanta Magazine
The Man Who Revolutionized Computer Science With Math
TED
How to Think Computationally About AI, the Universe and Everything | Stephen Wolfram | TED
Jeffrey Kaplan
Russell's Paradox - a simple explanation of a profound problem
Quanta Magazine
2020's Biggest Breakthroughs in Math and Computer Science