Emil Post

Abstract

Emil Leon Post (1897–1954), a one-armed New York mathematician, proved the completeness of propositional logic with truth tables in his 1920 doctoral thesis and, during a postdoctoral year at Princeton in 1920–21, reached the conclusion that no formal system could capture all of mathematics and that some problems have no mechanical solution, a decade before Gödel, Church and Turing. The discovery set off the first attack of the manic-depressive illness that disrupted his career, he published nothing on it, and when he wrote it up in 1941 the American Journal of Mathematics declined to print a historical account. His published work still shaped computer science: an abstract machine of 1936 independent of Turing’s, the string-rewriting “production systems” of 1943, the theory of recursively enumerable sets and degrees of unsolvability of 1944, the Post correspondence problem of 1946, now a standard tool for proving problems of formal languages undecidable, and the unsolvability of Thue’s word problem in 1947. He did most of it in three hours a day, with a teaching load of sixteen hours a week at City College.

Emil Leon Post. Image: public domain, via Wikimedia Commons.

Augustów to Harlem

Emil Leon Post was born on 11 February 1897 into an Orthodox Jewish family in Augustów, then in the Russian Empire and after 1918 in north-eastern Poland. His father, Arnold, emigrated to America the year Emil was born to join his brother in the clothing and fur business; in May 1904, when the business had prospered, Emil, his mother Pearl and his sisters Anna and Ethel followed. The family lived in a comfortable house in Harlem.

As a child Post wanted to be an astronomer. At twelve he reached under a parked car for a lost ball when a second car crashed into it, and he lost his left arm below the shoulder. As a high-school senior he wrote to several observatories to ask whether the handicap would prevent a career in astronomy; the replies were not all negative, but they discouraged him, and he turned to mathematics.

He attended Townsend Harris High School, a free school for gifted students on the campus of City College, and took a BS in mathematics at City College in 1917, tuition-free. As an undergraduate he had already done most of a paper on generalized differentiation, which he presented to the American Mathematical Society in 1923 and published in full only in 1930.

Truth Tables

From 1917 to 1920 Post was a graduate student at Columbia University, where Cassius J. Keyser ran a seminar on Whitehead and Russell’s recently published Principia Mathematica. A second influence was the philosopher C. I. Lewis, whose Survey of Symbolic Logic of 1918 described a mathematical system as “any set of strings of recognizable marks” derived from initial strings “by operations performed according to rules which are independent of any meaning assigned to the marks.” Post took the idea seriously: a logic could be studied as a game played with strings of symbols, from the outside.

His 1920 doctoral thesis, published in shortened form in the American Journal of Mathematics in 1921 as “Introduction to a General Theory of Elementary Propositions,” did exactly that for the propositional part of Principia. Post assigned each proposition a value, + for true and − for false, set out the tables for the basic connectives, and introduced the general truth-table method. He proved that a formula is provable in Principia’s propositional calculus if and only if its truth table is always +, which gave both the completeness of the system and a mechanical procedure to decide whether any formula is a theorem. (Paul Bernays had proved the same in an unpublished Göttingen thesis of 1918; Wittgenstein’s Tractatus introduced truth tables independently in 1921.) The journal accepted the paper on condition that it be cut by a third.

The paper also opened three lines that Post pursued for years. He classified which sets of connectives can express every truth function, the result now called Post’s lattice, published in full in 1941. He defined consistency and completeness for arbitrary systems of axioms and rules, the notions still called Post-consistency and Post-completeness. And he generalized two-valued logic to m values, shortly after Jan Łukasiewicz in Poland had proposed a three-valued logic, which made him one of the founders of many-valued logic.

Princeton, 1920–21

Post spent the academic year 1920–21 at Princeton as a Procter Fellow (a fellowship Alan Turing would hold in 1937–38). His plan was ambitious: to find a general method of deciding, for any system of the kind his thesis had studied, which strings it could derive. He reduced the general case through a series of transformations to systems of extreme simplicity, in “normal form,” whose rules only removed a string from the front of a word and attached another at the end.

On the way he met a problem that would not yield. In a tag system, a word of 0s and 1s is processed by looking at its first symbol, deleting a fixed number of symbols from the front and appending a string determined by the first symbol to the end; the question is whether the process, for a given starting word, ever terminates. Post found that even the system with rules 0 → 00 and 1 → 1101, deleting three symbols at each step, defeated him. The name came from a fellow student and colleague, B. P. Gill: one end of the string chases the other.

In the summer of 1921 Post turned the program upside down. He came to believe that his normal systems could represent every possible system of symbolic derivation, a claim equivalent to what is now called the Church-Turing thesis. If that was true, a diagonal argument showed that the decision problem for normal systems was unsolvable, and that no formal system could prove every true statement about what normal systems derive. “A complete symbolic logic is impossible,” he concluded. Post had in hand the essentials of Gödel’s incompleteness theorem of 1931 and of the undecidability results Church and Turing published in 1936, for systems of his own kind rather than for arithmetic.

He did not publish them. Post wanted first to give a complete analysis of “all finite processes of the human mind” that would make his thesis certain, a task he never finished. The excitement of the discovery brought on his first attack of manic-depressive illness. An earlier paper had been returned by the Annals of Mathematics “without any editorial commitment, and with a very mixed report from the referee,” and he concluded that it was hopeless to seek publication of the rest.

Illness

Post recovered enough to take an instructorship at Cornell in 1924, but a second attack ended his university teaching, and through the later 1920s he supported himself as a teacher at George Washington High School in New York. Under the care of a general practitioner, Dr. Levy, he followed a regime designed to prevent the excitement that brought on manic attacks: research was limited to three hours a day, from four to five in the afternoon and from seven to nine in the evening. In 1929 he married Gertrude Singer, who typed his papers and letters and managed the family’s affairs. “My mother … was the buffer in daily life that permitted my father to devote his attention to mathematics,” their daughter Phyllis later wrote. “Would he have accomplished so much without her? I, for one, don’t think so.”

In 1932 he was appointed to City College, left after a month, and returned in 1935, staying for the rest of his life with a teaching load of sixteen hours a week.

Gödel

On 28 October 1938 Post met Kurt Gödel at a meeting of the American Mathematical Society in New York and talked to him at length about his own work of 1921. The next day he sent Gödel a postcard of apology: “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 he might make, he added, the best he could say was that he would have proved Gödel’s theorem in 1921, had he been Gödel. The following day he wrote again, summarized what he had found, and ended with a judgement on himself: “after all it is not ideas but the execution of ideas that constitute a mark of greatness.” Gödel replied that he had noticed nothing of the “egotistical outbursts” Post feared, and that it had been a pleasure to talk with him.

In 1941 Post sent a long account of his postdoctoral work, “Absolutely Unsolvable Problems and Relatively Undecidable Propositions: Account of an Anticipation,” to Hermann Weyl, editor of the American Journal of Mathematics. Weyl declined: “I have little doubt 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; in the meantime Gödel, Church and others have done what they have done, and the American Journal is no place for historical accounts.” The paper appeared in 1965, eleven years after Post’s death, in Martin Davis’s anthology The Undecidable.

Formulation 1

In October 1936 Post submitted a three-page paper, “Finite Combinatory Processes: Formulation 1,” to the Journal of Symbolic Logic. It described a “worker” moving along a two-way infinite row of boxes, each marked or empty, who could mark a box, erase a mark, move one box left or right, and test whether the current box was marked, following a numbered list of instructions that ended with “stop.” It was, in all essentials, the machine Alan Turing had described in a paper received by the Proceedings of the London Mathematical Society that May (see Alan Turing and the Enigma). The journal’s editor, Alonzo Church, added a note that Post’s paper, “although bearing a later date, was written entirely independently of Turing’s” (see Alonzo Church and Lambda Calculus). The model is now called the Post machine, and the minimal instruction set of Post’s worker survives in the “Post-Turing machine” of textbooks.

Post objected to treating the identification of “effectively calculable” with these formal models as a mere definition. It was, he wrote, “a fundamental discovery in the limitations of the mathematicizing power of Homo Sapiens,” and needed continual verification. He planned further “formulations”; Turing’s fuller treatment overtook him. “Turing,” he noted in February 1938, had “in large measure removed what was left in my point of view.”

Production Systems and Degrees

The 1941 paper was rejected, but a shortened version of its first part appeared in the American Journal of Mathematics in 1943 as “Formal Reductions of the General Combinatorial Decision Problem.” It defined Post’s canonical systems and production rules, rewriting rules of the form “a string containing this pattern produces a string containing that pattern,” and proved that every canonical system could be reduced to one in normal form. Production systems became a basic model in several fields: Noam Chomsky’s formal grammars of the 1950s are production systems (see The Chomsky Hierarchy), and so are the rule-based expert systems of the 1970s. Post’s “unification process” in his attempts on tag reappeared as the unification algorithm of automated theorem proving.

In February 1944 Post gave an invited address to the American Mathematical Society in New York, published as “Recursively Enumerable Sets of Positive Integers and Their Decision Problems.” It is his most influential paper. Stripping recursion theory of its formalism, Post argued informally about sets of numbers that a machine could list, showed that there is such a set whose membership no machine can decide, and introduced ways of comparing unsolvable problems: one problem is reducible to another if a solution to the second would yield a solution to the first. Problems then fall into degrees of unsolvability. Post asked whether there were listable sets of intermediate degree, harder than any solvable problem but easier than the halting problem. He could answer the question for restricted kinds of reduction but not for the general one. Post’s problem drove recursion theory for a decade until two young mathematicians, Albert Muchnik in the Soviet Union in 1956 and Richard Friedberg in the United States in 1957, solved it independently with the “priority method” (see Automata Theory and Computability). Post’s reductions reappear, with time bounds added, in complexity theory.

The Correspondence Problem

In 1946 Post published a short note in the Bulletin of the American Mathematical Society, “A Variant of a Recursively Unsolvable Problem.” It posed a puzzle that a child could understand. Given a finite set of dominoes, each with one string on its top half and another on its bottom half, is there a sequence of them, repetitions allowed, in which the concatenated top strings equal the concatenated bottom strings? Post proved that no algorithm can answer the question for every set of dominoes, by reducing his normal systems to it.

The Post correspondence problem became a standard tool of theoretical computer science because it is so easy to embed in other problems. From 1961 it was used to prove that basic questions about context-free grammars are undecidable: whether a grammar is ambiguous, or whether two grammars generate any common string. It appears in textbooks of formal language theory, such as Hopcroft and Ullman’s.

In 1947 Post solved a problem that Axel Thue had posed in 1914: given a finite set of equations between words, can one decide whether two words are equal in the resulting semigroup? Post proved the problem unsolvable by translating Turing machines into the rewriting rules of what he named semi-Thue systems. The Russian logician A. A. Markov proved the same result independently, at almost the same time.

The Teacher

At City College Post was a popular teacher with unusual methods. His student Martin Davis, who became a leading logician himself, described his classes as “tautly organized tense affairs”: each period began with students putting assigned problems and proofs on the blackboard without book or notes, and “woe betide the hapless student who was unprepared,” who would face Post’s “more in sorrow than anger” look. Then Post took out his 3-by-5 index cards and explained the fine points; the class was a success if he finished the last card as the bell rang. Questions were discouraged, since there was no time. Several of his students, among them Davis, went on to become mathematicians.

In 1954 the illness returned. Post died of a heart attack on 21 April 1954, after electroshock treatment at a mental hospital in upstate New York, aged 57. In his diary he had written: “I study Mathematics as a product of the human mind not as absolute.”