Emil Leon Post turned thirteen on February 11, 1910. As a teenager growing up in New York City, he dreamt of being an astronomer. The big news in astronomy at that time was the return of Halley’s Comet that spring. Not only was this the first time the comet could be photographed, it was also the first time that spectrographic data would be available, providing clues about the comet’s composition.
Post could hardly have been unaware of the excitement. Newspaper coverage mixed scientific findings with legends about the comet as a harbinger of calamity. It was reported that the comet’s tail contained cyanogen, a toxic gas related to cyanide, and that the earth would pass through the comet’s tail. The result was mass hysteria. A French astronomer predicted the demise of all life on earth. Others suggested that the interaction of the comet’s tail with the earth’s atmosphere would trigger an explosion. Still others believed the mix would create laughing gas, ending the human race in a massive bout of hilarity.1
The earth’s brush with Halley’s Comet in May 1910 was not the cause of any major catastrophes. But some months earlier, and not long before his thirteenth birthday, a catastrophe had befallen Post. He lost an arm in a freak accident. While playing in a New York City street, he reached for a ball that had rolled under a parked car. A second car crashed into the first, crushing his left arm.
A few years later, as he was completing high school, Post wrote to a few observatories to inquire whether astronomy was a viable field for a person with only one arm. The replies were sufficiently discouraging that he decided instead to study mathematics.
A Creative Process
“The Logical Process is Essentially Creative,” Post wrote in 1941.
This conclusion … makes of the mathematician much more than a clever being … We see that a machine [emphasis original] would never give a complete logic; for once the machine is made we could prove a theorem it does not prove.2
The paper in which Post wrote these words recounted his insights from 1920–1921, which led him to conclude that all logical systems are incomplete. Every such system that is consistent contains a statement that is true, but that cannot be proved within that system.
Kurt Gödel’s landmark proof of incompleteness was not published until 1931.
Post had anticipated Gödel’s results by a decade.
It was around the time of his encounter with incompleteness that Post suffered his first attack of manic-depression, an illness now known as bipolar disorder. It was a malady that would plague him for the rest of his life. In the years that followed, the euphoria he experienced as a result of new mathematical insights sometimes became a trigger that pushed him over the edge into mania.
Despite these handicaps, Post produced work of profound insight and originality. He operated at an almost unimaginable level of generality. Where others tried to invent new axiomatic systems with enough bells and whistles to cover all of mathematics, Post sought to analyze all conceivable logical systems. His was no dry, mechanical enterprise: Post sought to understand logic as a human activity and to discover just how far its powers extended.
Never a mathematical star during his lifetime, Post created and pursued his research ideas largely on his own. In the decades since his death in 1954, the fundamental concepts he developed have proven exceptionally fertile, both by stimulating new research and by providing the framework for the pursuit of new ideas in other fields.
Inspiration
Post was born in Augustów, Poland, in 1897 to Orthodox Jewish parents, Arnold and Pearl Post. That same year, Arnold Post decided to join his brother in New York City. After establishing a successful clothing business, he sent for his family. In 1904, Emil, his mother, and his two sisters immigrated to the United States. The family settled in Harlem.
Post graduated from Townsend Harris High School, an institution for gifted boys that was attached to the City College of New York (CCNY). Having abandoned astronomy, Post majored in mathematics when he began studying at CCNY in 1914. The college became known as the proletarian Harvard because it charged no tuition fees and had high academic standards; its degrees commanded a great deal of prestige.
Post thrived at CCNY and began doing research while still an undergraduate. He examined how to interpret an nth-order differential operator when n is not an integer. The results he obtained, which were not published until 1930, include a method for inverting the Laplace transform that became known as the Post–Widder formula.
In 1917, Post began graduate studies in mathematics at Columbia University. His doctoral adviser, Cassius Keyser, was known less for his mathematical research than for his expositions of philosophy and mathematics. Erudite, insightful, and high-minded, Keyser wrote in an elaborate style that might now seem anachronistic. One can easily imagine the youthful Post being inspired by his eloquent and idealistic adviser. In several of his papers, Post cited Keyser’s influence.
Beneath the Surface of Common Sense
Bertrand Russell and Alfred North Whitehead published their three-volume opus, Principia Mathematica, between 1910 and 1913. The goal of the Principia was to show that all of mathematics could be deduced from a system of symbolic logic based on a small number of axioms. Writing in 1916, Keyser described Principia as “an amazing revelation of how the familiar terms [of mathematics and science] plunge their roots far into the darkness beneath the surface of common sense.”3
Many mathematicians believed that symbolic logic would furnish flawlessly rigorous methods for establishing or refuting any conceivable mathematical statement. If they could be sure that a logical system was sound and complete—meaning it never led to a contradiction and could prove or refute any statement—then the entirety of mathematics could be known. David Hilbert captured the zeitgeist in his 1930 declaration: “Wir müssen wissen. Wir werden wissen (We must know, we will know).”
While a graduate student, Post attended a seminar on the Principia and pored over the volumes page by page. Another major influence was A Survey of Symbolic Logic by C. I. Lewis, published in 1918. Lewis reproached Russell and Whitehead for “[taking] the laws of the logical relations of propositions for granted in order to prove them.”4 As an alternative to the Principia, Lewis proposed what he called the heterodox view. This was a radical, bare-bones conception of mathematics as merely “a set of strings of recognizable marks” and rules for operating on the strings. “This might,” he wrote, “be called the ‘external view of mathematics’ or ‘mathematics without meaning’.”5
Post took the heterodox view to heart. In a 1921 paper, he wrote that the Principia “gave up the generality of outlook which characterized symbolic logic.”6 Post’s goal was to recover that generality by representing formal logical systems as abstract mathematical objects to which mathematical methods could be applied.
In his PhD thesis, Post focused on a single restricted subsystem within the Principia, the propositional calculus. Sentences in the propositional calculus are represented as strings of variables that take the value 1 for true or 0 for false and that are connected by symbols for “not” and “or.” Post showed how, for any such string, one could set up a truth table which lists all possible combinations of the truth values of the variables. For each combination, the truth table specifies the truth value of the string. Ludwig Wittgenstein used truth tables in his Tractatus Logico-Philosophicus and so did Russell and Whitehead in the Principia. Post was the first to develop an analytical method based on truth tables. Using this method, he was able to prove that the propositional calculus of the Principia is both sound and complete.7
Post also carried out a generalization to many-valued logical systems, in which the number of truth values is greater than two. This class of systems, he remarked, “seems to have the same relation to ordinary logic that geometry in a space of an arbitrary number of dimensions has to the geometry of Euclid.”8 His work on many-valued logics stimulated further research, including extensions to their algebraic version, known as Post algebras.
Post at Princeton
Post spent the 1920 academic year on a Procter Fellowship at Princeton University. In a biographical article, Molly Gleiser wrote that he was “unhappy and isolated. … Princeton seemed like a foreign country after New York.”9 Post longed for the weekend and the train back to New York City, said Martin Davis, who as an undergraduate studied under Post.
Davis was also unhappy at Princeton when he was there as a graduate student in the 1940s. Among the comments he endured were admonitions to “stop acting like a Yeshiva boy around Fine Hall.”10 As the holder of a prestigious postdoctoral fellowship, Post was probably treated better than a graduate student, but he may also have encountered casual anti-Semitism.
During the period Post was at Princeton, mathematics in the United States was less developed than in Europe. This was especially true of logic, which was something of a mathematical backwater that made few significant advances during the 1920s. When Post was at Princeton, few mathematicians were engaged in research, and none of them worked in logic.
During this period it was common for Americans who had just received their PhD in mathematics to make a pilgrimage to Europe’s mathematical centers. This was the path taken by Alonzo Church, a near-contemporary of Post, who went on to become one of the outstanding logicians of the twentieth century. Church was an undergraduate at Princeton while Post was there. After completing his PhD, Church spent two years in Göttingen and Amsterdam, where he worked with two of the outstanding mathematicians of the time, Hilbert and L. E. J. Brouwer.
Post did not enjoy such advantages. His ability to travel was impaired by his psychological problems, and after entering the US in 1904, he appears never to have left again. “To a remarkable extent,” Alasdair Urquhart observed, “Post as a logician was a homegrown American original. … [A]fter the initial stimulus provided by Principia Mathematica, [he] created his own research project and problems more or less single handed.”11
Simple Systems
Post wanted to see how far he could push the view of formal logical systems as sets of symbol strings and rules for their manipulation. During his time in Princeton, he found a way to reduce these systems to a series of canonical forms, which represented logical systems as combinatorial objects.
One of these forms, which he called Canonical Form C, starts with a set of strings on a finite alphabet; a finite number of those strings are specified as primitive assertions in the logic. A separate collection of symbols represents connectives, and a finite set of production rules supplies an algorithm for carrying out logical inferences. The rules can be repeatedly applied to generate all valid formulas in the system.
Urquhart demonstrated the simplicity of Canonical Form C using an example whose alphabet is { p, ~, ∨, (,) }. These symbols designate the propositional variables of the system: negation, disjunction, and the operator forming ordered pairs. With the production rules P1 ⇒ ~P1 and P1, P2 ⇒ P1 ∨ P2, the resulting system generates all the formulas of the propositional calculus of the Principia with a single variable p.
The production rules of Canonical Form C came to be called Post production systems, and the sets that they generate are the recursively enumerable languages. Post production systems provide a powerful abstract framework that has permeated computer science. They supplied the syntax John Backus and Peter Naur used in the Backus-Naur Form, which was crucial in the development of the programming language ALGOL. They have also been widely used in designing expert systems and compilers.12
The first to apply Post production systems was Noam Chomsky, who found in them just the right structures for his revolutionary theory of the grammars of natural languages. Chomsky carried out this work in the 1950s, but he never met Post, who died in 1954. “Post is a much undervalued figure,” Chomsky said in an email message to me. “When I was a student, including 4 fellowship years at Harvard (1951–1955, mostly philosophy, logic), I never heard his name.” Chomsky learned of Post’s work from Paul Rosenbloom’s The Elements of Mathematical Logic, published in 1950, and from the work of Davis.
Made Simpler Still
Canonical Form C carries a great deal of power in a simple form. Is there something yet simpler? There is. Post discovered what he called normal form, for which a production system consists of a single primitive assertion. All productions operate by erasing an initial substring and appending a substring. Post’s normal form theorem says that any system in Canonical Form C can be reduced to one in normal form. Marvin Minsky described this as “one of the most beautiful theorems in mathematics.”13 Though he did not work out the details, Post knew that even the Principia, with its vast power and complexity, could be grown from the few seeds that constitute a normal form system. “Since Principia was intended to formalize all of existing mathematics,” Davis wrote, “Post was proposing no less than to find a single algorithm for all of mathematics.”14
A normal form production system resembles a combinatorial procedure that Post called tag. Consider the following example. We are given a string of 0s and 1s. If the first symbol is 0, append 00 to the string; if the first symbol is 1, append 1101. Erase the first three symbols of the resulting string, then repeat. Does the sequence ever halt? Despite several months of experimentation, Post was unable to find a conclusive answer for this particular example or for tag procedures more generally.
Years later, in light of his own work as well as that of Church, Gödel, and Alan Turing, among others, Post realized that tag was probably unsolvable. He suggested this possibility to Davis, who then mentioned it to Minsky. In 1961, seven years after Post’s death, Minsky proved the unsolvability of tag.
Post hoped to “close the circle” by showing that any normal form system could be reduced to his Canonical Form A—were that the case, a proof of the completeness of systems in any of the forms would immediately imply a proof for systems in all forms. Although he was hopeful that such a proof would work out, “certain of the difficulties of ‘tag’ even then seemed glimmering in the distance.”15 But then, he wrote, “a fuller realization of the significance of the previous reductions led to a reversal of our entire program.”
The Reversal
It was this reversal that led Post to incompleteness. He formulated what is now called Post’s thesis, a name chosen by Davis to echo the Church–Turing thesis, to which it is essentially equivalent. Post’s thesis applies to the intuitive idea of a generated set, which Post described as any set of symbols that can be “produced, created—in practice, written down.”16 Thinking of strings of symbols as statements in a formal axiomatic system, one can interpret a generated set as the theorems in that system. Post’s thesis states that, for any generated set, one can find a system in normal form that produces exactly that set.
By using a diagonal argument, Post was able to obtain a set, D, that seemed to be a counterexample to his thesis. But his experience with tag gave him the courage to make a momentous leap of faith: D is not a generated set. We can say today that D is not computable; that is, that there exists no algorithm that produces D as its output.
By using a mathematically rigorous version of his thesis, Post was able to conclude that:
A complete symbolic logic is impossible [emphasis original]. This is an iconoclastic result from the formal logician’s point of view since it means that logic must not only in some parts of its description … but in its very operation be informal.17
Contrary to the conception of Lewis, mathematics cannot be entirely reduced to a set of meaningless marks set down by mechanically following rules.
“Mathematical thinking,” Post declared, “is, and must be, essentially creative.”18
Surpassed by Gödel
Although he understood their significance, Post did not publish his results about incompleteness. In 1931, Gödel became the first to publish a proof of incompleteness of formal logical systems. Post’s reaction to Gödel’s achievement was a mix of disappointment and admiration. After they met for the first time in 1938, Post sent Gödel a postcard, confessing that
for fifteen years I had carried around the thought of astounding the mathematical world with my unorthodox ideas, and meeting the man chiefly responsible for the vanishing of that dream rather carried me away … As for any claims I might make perhaps the best I can say is that I would have proved [emphasis original] Gödel’s Theorem in 1921—had I been Gödel.19
There were several reasons why Post did not publish his results. One was the difficulty he had encountered in publishing his PhD thesis, which led him to believe that his subsequent work, being yet more revolutionary, would be unpublishable. Post also put off publication because he hoped to develop his ideas further, in particular by carrying out a psychological analysis of all finite mental processes. Another reason may have been his bipolar disorder, which first appeared in 1921.
Post’s work on incompleteness survives in an extraordinary manuscript he prepared many years later entitled “Absolutely Unsolvable Problems and Relatively Undecidable Propositions—Account of an Anticipation.” In 1941, the manuscript was submitted to the American Journal of Mathematics, where it was sympathetically rejected by the editor at the time, Hermann Weyl. “I have little doubt,” he wrote to Post, “that twenty years ago your work, partly because of its then revolutionary character, did not find its due recognition. However, we cannot turn the clock back … the American Journal is no place for historical accounts.”20 The journal did agree to publish a much shorter paper, containing only Post’s theorem that any system in Canonical Form C can be reduced to a system in normal form.21 Post’s “Anticipation” is briefly recounted in a footnote at the end of this paper. Sometime in the late 1940s, Post entrusted the “Anticipation” manuscript to Davis. It was not published until 1965, when it appeared in The Undecidable, a collection edited by Davis.22 He later included it in Post’s collected works, of which he was the editor, published in 1994.23
The “Anticipation” contains the remarkable testimony of a logician and mathematician who had pondered the phenomenon of incompleteness for two decades. The appendix draws upon Post’s notes and diary from between 1920 and 1922, the period during which he attempted to address the mysteries of mental processes. For example, he writes:
…a notion which should be very fertile indeed, i.e., that of the Psychic Ether. In so far as this contains the things which give meaning to symbols it is just the unconscious … it is the seat of the birth [emphasis original] of new ideas; it is also the region where all the vaguer processes operate especially intuition, “hunches” etc. When these become precise they crystallize from the psychic ether. Clear symbolizations are then to be regarded like atoms in this ether. In fact one may think of them as Kelvin thought of his vortex atoms in connection with the lumeniferous ether.24
Gödel’s copy of The Undecidable sits on a shelf in the mathematics library of the Institute for Advanced Study, where he was a member of the faculty from 1940 until his death in 1978. It seems that Gödel read the “Anticipation” with keen interest. He covered most of the first page of the book with handwritten notes about the paper.25 Among his annotations, Gödel noted the pages on which the passage quoted above appears, and added: “Psychic Ether (= Intelligent Agents?).”
Gaining Stability
After leaving Princeton, Post took up a position at Cornell University. A second bipolar attack forced his departure. He then found himself unemployable in academia. Returning to New York City, he survived by teaching high school. Although his mental instability made finding a permanent position difficult, the anti-Semitic attitudes that were prevalent in academia at the time may have also been a factor.
Lewis Feuer, a CCNY graduate and PhD student at Harvard under Whitehead, mentioned Post in an article about anti-Semitism in academia.26 According to the article, Paul Saurel, who was the head of CCNY’s mathematics department for the thirteen years until his death in 1932, “refused to appoint Jews… Not until the appointment of Emil L. Post … was the anti-Semitic obstacle overcome.”27 Post was hired by CCNY in 1932, but within a month of his appointment, he suffered yet another bipolar attack. It was not until 1935 that he had recovered sufficiently to resume his position. Post remained at CCNY for the rest of his career.
Post’s slow climb to mental stability was aided by his wife, Gertrude Singer, whom he married in 1929. A daughter, Phyllis, was born three years later. She later wrote of her family:
My father was a genius; my mother was a saint … she was the buffer in daily life that permitted my father to devote his attention to mathematics (as well as to his varied interests in contemporary world affairs). Would he have accomplished so much without her? I, for one, don’t think so.28
Surpassed by Turing
Between the years 1921 and 1935, Post published nothing in logic. In 1936, he published a groundbreaking paper, only to be surpassed once again, this time by Turing’s landmark work on computable numbers, which appeared almost simultaneously.
Post’s paper “Finite Combinatory Processes—Formulation I,” appeared in one of the first issues of the Journal of Symbolic Logic, founded by Church.29 In Post’s formulation, a worker moves along an infinite line of boxes, carrying out a computation using only what he called “primitive acts” of marking or unmarking the boxes.30 His purpose was “not only to present a system of a certain logical potency but also, in its restricted field, of psychological fidelity.”31
There is a clear similarity between Post’s formulation and the infinite tape of a Turing machine; indeed, the two concepts are equivalent. The main difference is that Turing conceived of an actual physical device, whereas Post focused on the instructions a worker carries out. One might say that Turing conceived hardware, and Post conceived software. The concept is credited to Turing because he provided a more complete and comprehensive analysis of how to capture the intuitive notion of calculability in precise mathematical terms.
Turing’s paper runs to thirty-five pages, Post’s, to just three.32 Although his paper foreshadows work that he hoped to carry out, Post did not publish anything further on this subject. Among Post’s notebooks, which are housed at the American Philosophical Society in Philadelphia, musings can be found concerning “Formulation 2,” where “he considered rules operating in a two-dimensional symbol space, somewhat reminiscent of later work on cellular automata, such as Conway’s Game of Life.”33
Not a Definition, a Natural Law
In that same year of 1936, and before the papers by Post and Turing appeared, Church published his own paper, leading to what is now known as Church’s thesis: a function is intuitively calculable if it is recursive or if it can be represented in the λ-calculus, a formal system that Church had invented for expressing computation. He went further, suggesting that calculability could be defined as recursiveness or λ-calculability.
Post objected to Church’s approach. He argued that identifying calculability with a precise mathematical concept should not be called a definition. Instead it was a “working hypothesis.” If verified in sufficiently many real-world situations, it would rise to the level of a natural law.
[T]o mask [the identification of calculability with a mathematical concept] under a definition hides the fact that a fundamental discovery in the limitations of the mathematicizing power of Homo Sapiens has been made and blinds us to the need of its continual verification.34
Post pressed his point further in a 1937 letter to Church:
I—to put it crudely but forcibly—am willing to bet a 1000 to $1 that [there are no effectively calculable functions that are not recursive], and it would take me five years to save up that sum … But I am not willing to stake my “immortal” soul in it—which I should were I to adopt your [Church’s] original position [the thesis as a definition].35
As Vladimir Uspensky wrote in Post’s Machine, “The substantiation of Post’s ‘working hypothesis’ took a path that is more traditional for a naturalist than for a mathematician, that is, an experimental path supported by conceptual arguments.” Long experience with algorithms and computing have led to the conviction that it is impossible to devise an algorithm that cannot be represented by Post’s machine. As Uspensky put it, Post’s belief that his working hypothesis would eventually have the status of a natural law “can be thought to have come true.”36
Post’s Teaching
The working conditions that Post endured at CCNY were difficult. His teaching load required him to be in the classroom sixteen hours a week. He had no office; the whole mathematics faculty shared a single room with a big table in the middle. He also had no secretary. If Post needed a letter of recommendation typed, he or his wife did it.
Despite these pressures, Post was an outstanding and popular teacher. An article in the New York Times quoted Herbert Hauptman, who was a math major, as saying of Post, “Oh, he was fantastic! He taught me number theory. He was very strict and tolerated no nonsense whatsoever.”37 Hauptman was probably referring to Post’s classroom format, wherein students had to make blackboard presentations about the course material without consulting any notes or books. “Woe unto the student who simply reproduced the textbook proof,” another Post student, John Stachel, wrote in an email message to me. “Post would simply tear the argument to pieces. That is how I learned what constituted a real proof of a mathematical theorem.”
If there was time at the end of class, Post would refer to a stack of three-by-five index cards and discuss some fine points. Citing lack of time, he discouraged questions. But his explanations were so clear and thorough that he reached both strong and weak students.38 He was fanatical about making good use of class time. Gleiser recalled him seriously reassuring a class: “We are doing very well. We are 10 minutes ahead of where this course was last year.”39
Considering the demands of his job and his handicaps, Post was an incredibly productive researcher. Since he had no office, according to Davis, he did his research “sitting at a desk in the living room of his small apartment while his young daughter was required to maintain silence.”40 Although Post’s best-known publications are in logic, his mathematical interests were wide ranging. In addition to two early papers in analysis, abstracts of lectures he presented indicate an interest in geometry. While the breadth of his mathematical ambitions and the sweep of his ideas mark him as a consummate theory builder, Post was also a great problem solver who enjoyed working on the problems in the Putnam Competition, a contest for mathematically talented undergraduates.
Post’s longest paper, published in 1940, was not in logic but algebra.41 The topic was polyadic groups, a generalization of the concept of a group in which the group operation, instead of being dyadic (a function of two variables) can be polyadic (a function of any finite number of variables). Post described and analyzed the class of polyadic groups so thoroughly that his paper essentially closed the subject.42
Into the Mainstream
No medications were available to treat Post’s bipolar illness. Because he was more prone to elation than depression, a doctor recommended a practical regime to avoid shocks and surprises by making daily life totally routine. Post would wake up at 6:00 a.m., teach in the morning, and return home for lunch and a nap. He would then do mathematics until exactly 5:00 p.m. and go for a walk afterward. “[H]e was always quite annoyed if he met anyone,” Gleiser wrote, “since the main purpose of his walk was to clear his mind.”43 An after-dinner mathematics session ended promptly at 9:00 p.m., after which Post took another walk. Bedtime was 10:00 p.m. He also made sure to have two different projects going, so that if one became too exciting, he could switch to the other.
Although Post’s notebooks show that he worked ceaselessly on mathematics, his published output is modest. Of the dozen papers published during his lifetime, about half of them were from the 1940s. These included his most influential paper, “Recursively Enumerable Sets of Positive Integers and Their Decision Problems,” which established the theory of recursive unsolvability as a branch of mainstream mathematics.44
One of the reasons the paper had such an impact is that it provided an informal, intuitive introduction to the theory of general recursive functions. Early in the paper, Post stated that mathematicians were mostly oblivious to the significant contributions made by Church, Gödel, and Turing. This was partly due to “the forbidding, diverse, and alien formalisms in which this work is embodied.” He sought to strip away some of the formalism and present an intuitive development that would allow a mathematician, “layman though he may be in this formal field,” to follow and perhaps even develop it.45
A set is called recursively enumerable if there is a recursive function—for example, an integral polynomial function—that, when fed integers, outputs the members of the set. The decision problem for a recursively enumerable set asks whether there is a procedure for deciding, given an arbitrary integer, whether that integer is a member of the set. One counterintuitive yet fundamental result of recursive function theory, due to Church and his two students, Stephen Kleene and Barkley Rosser, is that there exists a recursively enumerable set whose decision problem is unsolvable. One can list the elements of the set, but there is no way to decide whether an arbitrary integer is in the set.
The most original aspect of Post’s paper is his vision of how decision problems are related to one another. This has broad consequences, because many problems can be transformed into decision problems for recursively enumerable sets. A central theme is the reducibility of one problem to another. If a problem P is reducible to a different problem Q, then a solution to Q will furnish a solution to P. Conversely, if P is unsolvable, then Q is unsolvable as well, and we say that P has a lower degree of unsolvability than Q. Post’s paper envisions a web of relationships among unsolvable problems, seeking those of the lowest possible degree—the problems that are in some sense the most fundamentally unsolvable.
The paper spawned a great deal of development of the various kinds of reducibility Post introduced. What came to be known as Post’s Problem explored the question of intermediate degrees of unsolvability under the most general kind of reducibility, what Post called Turing reducibility. Post’s Problem was eventually solved in 1956 by A. A. Muchnik, and independently in 1957 by Richard Friedberg.
This paper also had a major impact on theoretical computer science, a field that did not exist during Post’s lifetime. “Modern complexity theory,” Davis notes, “is largely based on the paradigms introduced in [Post’s] paper.”46 Post’s vision of a web of unsolvable problems is apparent in what is arguably the central open problem in theoretical computer science today, the question of whether P = NP. Given a problem for which a solution can be verified in polynomial time, can the problem also be solved in polynomial time? This is a version of Post’s question about degrees of unsolvability in which the notion of recursively enumerable function is replaced by polynomial-time computable function.
Unsolvable Problems
A classic problem Post mentions in the paper is Hilbert’s Tenth Problem. Given any polynomial equation with integer coefficients and a finite number of unknowns, is there an algorithm to decide whether the equation has a solution in the integers? Post wrote that the problem “begs for an unsolvability proof.”47 When Davis heard about the problem, he was immediately seduced. The proof of its unsolvability was completed in 1970 by Davis, Yuri Matiyasevich, Hilary Putnam, and Julia Robinson. It is a landmark in twentieth-century mathematics.
In 1947, Post proved the unsolvability of the word problem for semigroups. In this context, a word can be thought of as a finite string of letters from a finite alphabet, like ba, abc, ca, cba … One is given a set of equations using the semigroup operation, such as ba = abc, bc = cba … . The word problem asks whether an arbitrary word can be deduced from the given equations. Post’s proof of the unsolvability of the word problem led to unsolvability results in other areas of mathematics, such as group theory and topology.
In the same year that Post proved the unsolvability of the word problem, he organized a reading course in logic at CCNY for Davis and his fellow undergraduate, John Stachel. One day Post burst in, boiling over with excitement about a new discovery he had just made about incomparable degrees of unsolvability. He told Davis and Stachel to stop what they were doing so that the three of them could work together on the discovery. Post had entered one of his manic phases. A day or two later, when his mania peaked, he began raving to his calculus class about the danger of sexual repression. Post was shepherded home by a student from the class. Shortly thereafter he was institutionalized.
Beset by bouts of his illness and by technical difficulties, Post sent his work on incomparable degrees of solvability to Kleene, who was then at the University of Wisconsin. Kleene greatly strengthened the results, and the resulting paper, which was published in 1948, was Post’s only paper with a coauthor.48
Undecidable Propositions
Many logicians and mathematicians have a dry, formal writing style. Post did not. Despite an emphasis on technical precision, his prose has a compelling intensity. His many footnotes contain not only side comments but also illuminating perspectives on his thinking. In the “Anticipation” manuscript, much of the story can be found in the accompanying 120 footnotes. The very first reveals a major mystery he hoped to understand: “A fundamental problem is the question of the existence of absolutely undecidable propositions.”49
Post hoped that, just as there is an absolute concept of computability, there would also be an absolute concept of provability of arithmetic propositions—those expressible in terms of logical operations and addition and multiplication of integers. Then, just as having an absolute concept of computability has led to provably unsolvable problems, so having such an absolute concept of provability would lead to a provably undecidable arithmetic proposition, one whose truth value we would never know.
Gödel’s incompleteness theorem guarantees the existence of an undecidable proposition in any logical system, but the undecidability is only relative to that system. If one augments the system by adding the undecidable proposition as an axiom, a new undecidable statement arises in the augmented system. “[W]e are confronted with a strange situation,” Gödel remarked in a 1933 lecture:
We set out to find a formal system for mathematics and instead of that found an infinity of systems, and whichever system you choose out of this infinity, there is one more comprehensive, i.e., whose axioms are stronger.50
Post made notes about a 1938 conversation with Gödel, in which Post suggested the prospect of an absolutely undecidable proposition. “Gödel pooh-poohed idea,” Post wrote. “Said (roughly) it was absurd.”51 Later Gödel’s thinking changed, and he eventually considered the possibility that such propositions might exist.
In a 1946 lecture, Gödel noted that solvability (or computability) is independent of the formal system in which one is working, a fact that he described as “a kind of miracle.”52 He suggested that this should encourage the expectation that the same kind of absoluteness might be possible for decidability and for definability, the question whether sets can be defined in a way that is independent of particular set-theoretic axioms.
Post held exactly this expectation. One of his last published pieces was a lecture abstract, dated February 9, 1953, which considered the question of absoluteness in the three realms of solvability, definability, and provability.53 According to Davis, few people today are working on the question of absolutely undecidable propositions, because developments in logic over the past half-century have made the prospect of absoluteness seem ever more elusive. At the same time, no evidence has surfaced to rule it out.
The Infinite and the Eternal
Post wrote not only mathematics, but also poetry. His last poem, entitled Ode to God, ends: “So great our pain Oh Lord above, What must thine be for those you love.” Post’s pain ended on April 21, 1954. He died after suffering a cardiac arrest following the administration of shock treatment for his mental illness. He left behind not only the profound insights his work revealed, but also the inspiration of his life.
Keyser described mathematics as “the most precious response that the human spirit has made to the call of the infinite and the eternal.”54 As a youth, Post felt this call when he yearned to be an astronomer. It stayed with him throughout his life. His work displayed supreme technical mastery of a highly technical subject. But his thinking never strayed far from the flesh and blood enterprise that is human mathematics.55
