Celebrating Emil Post & His "Intractable Problem" of Tag: 100 Years Later
Wolfram・162 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
Summary
00:00
Emil Post's Problem of Tag: Mathematical Complexity
- Stephen Wolfram introduces Emil Post and his problem of tag, highlighting the mathematician's interest in fundamental questions about mathematics.
- Post was born in 1897 in Poland, grew up in New York City, attended City College, and pursued a PhD in mathematics at Columbia, focusing on the foundations of logic.
- Post aimed to understand the underlying primitives of mathematics beyond basic logic operations, similar to computational language design principles.
- Post's work around 1920 predated the existence of computers and Turing machines, focusing on simplifying mathematics to string rewriting operations.
- Post identified a specific class of string rewritings, termed the normal form, simplifying complex mathematical expressions to string rewriting operations.
- The central question Post posed was determining the equality of two mathematical expressions through sequences of string rewritings.
- Post's experimental mathematics led to the development of the problem of tag, involving rewriting strings based on specific rules.
- The problem of tag involved applying rules to strings of ones and zeros, leading to either termination or cycling of the string.
- Post's calculations on the problem of tag revealed the complexity and unpredictability of the outcomes, with some cases taking thousands of steps to terminate.
- Post concluded that the general problem of tag seemed insurmountable, leading to a sense of hopelessness in solving finiteness problems through this approach.
17:22
Post's Contributions to Universal Computation Theory
- Post encountered mental health issues in late 1921, leading him to teach high school in New York City before becoming a professor at City College in 1935.
- Post's work in 1921 introduced computational irreducibility, a concept later expanded upon by Godel's theorem and Alonzo Church's lambda calculus in 1935.
- Post's 1936 paper closely approached defining Turing machines, highlighting the formal idea of computational processes and their connection to physical possibilities.
- Post's subsequent publications in mathematical logic, including the post-correspondence problem and polyatic groups, culminated in his 1943 paper on the general combinatorial decision problem.
- The problem of tag, named after a colleague's suggestion, delved into the concept of computational universality, where simple rules can lead to complex behavior.
- Post's observation of universal computation in a practical problem challenged the notion that complex constructions were necessary for achieving universality.
- Marvin Minsky's interest in tag systems in the 1950s coincided with the rise of generative grammars and early computer languages, sparking discussions on neural networks and artificial intelligence.
- Minsky's exploration of tag systems led to the simplification of the problem to its core elements, paving the way for universal computation and the development of reduced instruction set computers.
- Minsky's use of tag systems to generate simple universal Turing machines underscored the significance of string transformations in computation.
- The application of transformation rules, as seen in tag systems, extends beyond mathematics to represent computations in various fields, including the foundational principles of physics, demonstrating the universality of transformation rules in the universe.
34:25
Emil Post: Mathematician Ahead of His Time
- Emil Post may have been ahead of his time in understanding meta-mathematics in physical terms, similar to computation.
- Post's significant achievement was deriving computation from basic principles, observing computational irreducibility.
- Post's exploration of computational irreducibility in a specific tag system raises questions about its depth and potential implications.
- Emil Post, a mathematician, was born in 1897 in Poland and later moved to New York, where he married Gertrude Singer in 1929.
- Post's strict daily schedule included specific meal times, teaching routines, and research periods, followed by walks and family activities.
- Post had diverse interests, including sketching movie stars, astronomy, and a love for baseball, particularly the New York Giants and Yankees.
- Post's bipolar disorder, managed through a strict schedule, impacted his career in mathematics, leading to hospitalizations and eventual death in 1954.
- Post's family, including his daughters Gail Cayden and Marsha Emily Post, shared personal anecdotes and insights into his life and habits.
- Post's commitment to education and academic excellence led to the establishment of a scholarship in his name at City College, emphasizing his values.
- Post's meticulous timekeeping and habits, including sketching, strict schedules, and academic achievements, reflected his dedication to intellectual pursuits and overcoming challenges.
52:11
Post's Academic Journey and Family Connections
- Post's academic journey began at Brooklyn College before moving to City College, where he delved into writing about Jesse Douglas and astronomy.
- Post's connection to Jesse Douglas and astronomy is questioned, as there seems to be no apparent link between the two.
- Post's parents married in 1956, after Emma had passed away, and his father met Grandpa Emel at City College while chatting with friends, including Martin Davis.
- Post's father noted Professor Post in passing during his college days but did not have a significant interaction as he had not yet met Post's mother.
- Post's father and Professor Post did not meet until several years later, coincidentally when they established a scholarship at City College.
- Post's mother believes that Post's hypomania fueled his creative thinking, although his excitement sometimes led to true mania, hindering his progress.
- Post's mother never openly discussed Post's bipolar disorder, and Post was hospitalized from 1932 to 1935, leading to an absence in his daughter's life during those years.
- Post's hospital sketches were detailed and time-stamped, reflecting his meticulous nature and the impact of stressors like his daughter's birth on his mental health.
- Post's daughter inherited his drawing skills, creating sketches similar to his, but did not inherit his mathematical prowess.
- Post lived in Princeton but spent weekends in New York, where he was not content, highlighting the challenges of his work environment compared to modern-day complaints about working from home.
01:10:25
"Formalizing Mathematics: Seeking a Single Algorithm"
- Post 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 the method's lack of concern for meaning.
- Post created canonical forms A and B, simplifying Principia's complexities to reveal the core problem.
- Despite efforts to bridge solved problems with canonical forms, auxiliary problems arose, resisting solutions.
- Post encountered a problem of tech, showcasing the challenge of combinatorial iteration.
- He shifted focus to proving that mathematics might be unsolvable, leading to the development of canonical form C and the normal form.
- The normal form theorem demonstrated that all of mathematics could be reduced to a simple form.
- Post's first thesis suggested that any set of sequences solvable by a finite process could be generated by the normal form.
- Post's second thesis aimed to show that solvability in the intuitive sense aligned with solvability by his formulation one.
- Post's emphasis on finite processes over computability led to systems more relevant to computing and programming than Turing machines.
01:28:52
Emil Post's Mathematical Legacy and Personal Struggles
- The letter discussed the author's mental struggles and personal history, originating from a tech problem at Princeton.
- The author revealed his mental ups and downs to his wife for the first time in the letter to church.
- The letter was written in 1943, detailing the author's experiences and reflections at 50 years old.
- The author expressed a diminished personal importance of success or failure with 20 years left to live.
- The letter hinted at a significant problem the author faced, impacting his mental state.
- Emil Post, a mathematician, was influenced by logicians like Lukasiewicz and Polish logicians.
- Post's work was associated with minimalism, similar to Lukasiewicz's approach.
- Post's postdoctoral fellowship at Princeton was an honorary award, providing him with resources to work independently.
- Post's work on many-valued logics, like combinators, was significant in mathematical logic.
- Post's psychological approach to analyzing sequences stemmed from his canonical systems' limitations and the need for a human perspective.
01:50:25
Post's Creative Logic Project: Absolute Undecidability
- Post taught an honors course with a 16-hour weekly teaching load, meeting once a week for 2-3 hours, focusing on real variable theory.
- The teaching method involved students reproducing theorems and proofs from Townsend's pages and notes on the blackboard without notes.
- Post agreed to an honors reading course on logic with students John Statchell and the textbook was Alonso Church's pamphlet from the Annals of Mathematics series.
- The course covered the deduction theorem and propositional calculus, coinciding with Post's breakthrough on unsolvability degrees.
- Post's work on fractional differentiation led to the Post-Lidder formula for the inverse of Laplace transforms in 1930.
- Post's dissertation included a monograph on two-valued iterative systems of mathematical logic, later published in 1921.
- Post's significant paper on polyatomic groups in 1940 proved every group was isomorphic to a coset of an ordinary group, ending further research on the topic.
- Post sought an absolute notion of proof for arithmetic sentences, aiming to find undecidable propositions, distinct from Godel's undecidable propositions.
- Post's creative logic project aimed to find an absolute undecidable statement, distinct from finite processes, emphasizing the creative process of setting up finite processes.
- Post's notebooks on creative logic delve into the analysis of finding anchors in the mind for creative processes, focusing on the creative process of reaching conclusions beyond mere writing activities.
02:13:40
Martin's Journey: Metaphysics to Mathematics Evolution
- Martin discusses the potential convergence of metaphysics and mathematics, suggesting that if achieved, mathematics might cease to exist as we know it today.
- Questions from a live stream audience inquire about Martin's work on the ORDVAC computer and its connection to his teaching.
- Martin recalls developing a program in 1951 to track and navigate 100 airplanes in real-time using machine code on the ORDVAC computer.
- The program faced challenges due to the computer's lack of a clock, requiring precise timing calculations for radar data reception.
- Collaborating with physicist Marius Cone, Martin overcame technical hurdles, including trigonometric function computations.
- Martin later transitioned to the Institute for Advanced Study, where he worked on the Pressburger arithmetic program and the satisfiability problem with Hillary Putnam.
- The satisfiability algorithm developed with Putnam remains influential in the field, with variations still used in competitions.
- Martin reflects on his first encounter with the ORDVAC computer, describing its memory structure, input devices, and room-filling size.
- The ORDVAC's unique memory system, utilizing cathode ray tubes and a read-around process, posed challenges during program debugging.
- An anecdote highlights Martin's transition from formalisms influenced by Post's work to embracing Turing machines for their deterministic elegance and computational efficiency.
02:36:19
"Curry's Programming Innovations and Computer Science History"
- A mathematician named Curry was involved in a project alongside other individuals, including an English man with advanced ideas who developed a proto-assembly language allowing decimal number entry.
- Don Gillies, who later worked with the Institute machine, had a clear concept of a programmer's capabilities and was critical of John Weinman's understanding.
- Von Neumann, despite having 25 computers at his disposal, did not grasp the concept of recursive computer use or subroutines, unlike Curry who was already advanced in programming in the late 40s.
- Curry's work on combinators intersected with his practical computing involvement, showcasing his innovative thinking in programming.
- Von Neumann's procedural programming approach contrasted with Curry's functional programming ideas, with the former not comprehending the role of the stack and subroutines.
- Martin Davis shared anecdotes about meeting Von Neumann and Shannon, highlighting their personalities and interactions at Bell Labs.
- Shannon's playful nature and love for relays led to amusing incidents like building machines to play games against each other.
- Davis discussed the technical side of solving the Tag problem, contrasting the manual work of the past with the computational capabilities available today.
- The Tag problem's complexity varied with input length, with sudden increases in steps required for a conclusion, prompting the exploration of all possible initial conditions.
- Davis mentioned having an essay detailing 70 years of computer science history, showcasing his knowledge and contributions to the field.
02:55:41
"Evolution of tag systems and universal computation"
- The evolution of a system where strings grow and eventually cycle is explored.
- Strings of varying lengths evolve into cycles of different sizes.
- A map of possible string evolutions is depicted, showing different outcomes.
- Larger initial conditions lead to long highways before reaching a cycle of size 28.
- The question of whether all initial conditions lead to termination on a cycle is raised.
- Examples of strings terminating after specific steps are shown.
- The potential for universal computation in tag systems is discussed.
- A tag system capable of emulating a universal Turing machine is presented.
- The possibility of simpler tag systems being universal is considered.
- The resemblance of tag system behavior to random walks is analyzed.
03:11:06
"Charity Engine aids in solving mathematical problems"
- The post tag system can either terminate or run indefinitely, with initial conditions affecting its behavior.
- Initial condition 101 leads to a cyclic pattern after some random bouncing around.
- At initial condition 469, the system may not terminate even after a million steps.
- The post tag system resembles the three n plus one problem, with some initial conditions causing non-termination.
- A specific initial condition took 643 billion steps before terminating in a cycle of size 10.
- Charity Engine, a crowd-sourced cloud computing platform, aids in large-scale computations for scientific research.
- Charity Engine assisted in solving diophantine equations, showcasing undecidability in mathematics.
- Charity Engine's collaboration with Stephen Wolfram aims to crack the tag system problem.
- Large-scale searches evaluate post's tag system rule across all possible initial conditions of varying lengths.
- The search process involves a chase phase followed by pounce phases to narrow down potential non-terminating initial conditions.
03:27:03
Unsolved computational challenges and infinite complexities
- The source code for the batch job is available on GitHub, with a link provided in the live stream chat for anyone to access and run it.
- The batch job involves running large computations, with one case reaching 12 trillion steps and another at 205 trillion steps and still running.
- Despite extensive computational efforts, the problem remains unsolved, highlighting the concept of computational irreducibility.
- The goal is to continue working on solving the problem to gather evidence for the principle of computational equivalence.
- Computational irreducibility poses significant implications for science, emphasizing the limitations and complexities involved in understanding systems.
- Examples of computational challenges, such as the distribution of primes and word equations, illustrate the difficulty of inferring infinite outcomes from finite computations.
- The concept of computational irreducibility also plays a role in defining the passage of time and the significance of ongoing computational processes.
- The history of attempts to solve complex computational problems, like Hilbert's 10th problem, showcases the challenges posed by undecidability and the vastness of infinity.
- The discussion concludes with a hope to eventually solve the complex computational problem at hand, acknowledging the enduring nature of such challenges in computational history.
