Emil Post
Emil Leon Post (1897–1954) was an American mathematician and logician whose work on computability, undecidability, and formal systems places him among the four founders of modern computation theory — alongside Alan Turing, Alonzo Church, and Kurt Gödel. Where Turing gave the world the machine and Church gave it the lambda calculus, Post gave it a grammar: a way to generate the computable rather than merely describe it. His inventions — Post's Problem, Post canonical systems, and the theory of degrees of unsolvability — remain active research areas, yet his name circulates far less than his contributions warrant. This is not accidental. Post's career was interrupted by mental illness, his publications were sparse, and his style was rigorous to the point of austerity. History remembers the propagandists; Post was a cartographer of the boundary between what can be computed and what cannot.
The Incompleteness Theorem, Independently
Post's earliest significant result came in 1921, a decade before Gödel, in his doctoral dissertation at Columbia University. Working on the completeness of propositional logic, Post developed a method of truth-tables and demonstrated that the propositional calculus is both consistent and complete — every valid formula is provable. But he also saw, and recorded in private notes, that the same methods could not be extended to more powerful systems. He understood that any sufficiently strong formal system would contain undecidable propositions. This was the essence of Gödel's incompleteness theorem, arrived at independently and earlier, though Post did not publish it. Gödel's 1931 paper won the priority race; Post's unpublished anticipation became a footnote. The episode illustrates a recurring pattern in Post's life: he saw the landscape before others, but he refused to claim it until he had mapped every ridge and valley.
Post's Problem and the Degrees of Unsolvability
The central achievement of Post's mature work was the articulation of what became known as Post's Problem: whether there exist recursively enumerable sets whose degree of unsolvability is strictly between the decidable and the complete (the halting problem). Post formulated this in 1944, and it remained open for twelve years until it was solved independently by Richard Friedberg and Albert Muchnik in 1956, using the method of finite injury priority arguments that Post had anticipated but not executed.
The framework Post developed to state the problem — the theory of degrees of unsolvability and Turing reducibility — turned out to be more important than the problem itself. Post showed that undecidability is not a single condition but a structured landscape. Some undecidable problems are strictly harder than others; some are incomparable. The degrees of unsolvability form an algebraic structure — the Turing degrees — that has been studied ever since as a way of measuring the information content of computational problems. Post's problem was the question that launched this field.
Post Canonical Systems and Formal Language Theory
In the 1920s and 1930s, Post developed what he called canonical systems: rule-based generative schemes for producing strings from strings. A canonical system consists of an alphabet, an initial string, and a finite set of substitution rules. Post proved that every recursively enumerable set can be generated by a canonical system — a result equivalent to the equivalence of Turing machines and Church's lambda calculus but expressed in purely syntactic, grammatical terms.
This formulation anticipated by decades the generative grammars of Noam Chomsky. Chomsky's hierarchy of formal languages — regular, context-free, context-sensitive, and recursively enumerable — is, in retrospect, a classification of restricted Post canonical systems. Post had already shown that the full systems generate exactly the computable-enumerable sets; Chomsky's contribution was to show what happens when you restrict the rules. The intellectual lineage is direct, though rarely acknowledged in linguistics textbooks. Post's systems are the universal engine; Chomsky's hierarchy is the taxonomy of its throttled variants.
Life, Illness, and Legacy
Post was born in Poland and emigrated to the United States as a child. He lost an arm in an accident at the age of twelve, an event that may have intensified his already remarkable concentration. He suffered from manic-depressive illness (now bipolar disorder) and was institutionalized multiple times. His periods of productivity were intense and his periods of incapacity were severe. He mentored Martin Davis, who became one of the central figures in American logic and who carried Post's program forward through the 1950s and 1960s.
Post died of a heart attack in 1954, shortly before the solution to his famous problem. He did not live to see the flowering of computability theory as a major branch of mathematics, nor the absorption of his canonical systems into computer science and linguistics. His work on the boundary between the computable and the non-computable remains a foundational constraint on any theory of machine intelligence, any cybernetic system, and any systems-theoretic account of what information processing can and cannot achieve.
The standard history of computation theory is written as a duet between Turing and Church. Post is relegated to the role of a talented accompanist. This is a historiographical failure as serious as any technical error. Post's canonical systems reveal that computation is not merely mechanical procedure — it is syntactic generation. The difference is not pedantic. A Turing machine is a device that executes; a canonical system is a grammar that produces. One is engineering; the other is language. If we are building minds from language models rather than from registers and tapes, then Post's grammar-first approach to computability was not a minor variant. It was the road we would eventually take — and we took it without knowing whose path we were walking on.