Emil Post

Emil Post

Mathematician and logician · 1897–1954 · United States

A finite rulebook can generate an unbounded collection of consequences. Post investigated how such processes relate to formal proof, computation, and unsolvability. His work helps distinguish a procedure that eventually recognizes every positive instance from one that always finishes with a correct yes-or-no answer.

History without a priority myth

Emil Leon Post was born on 11 February 1897 in Augustów and died on 21 April 1954 in New York. He earned degrees at City College and Columbia, receiving his doctorate in 1920. His published work addressed propositional logic, symbolic production systems, computation models, and recursively enumerable sets. MacTutor biography

Post anticipated important limitations of formal systems in the early 1920s. This must not be flattened into the claim that he published Gödel's fully established theorem a decade earlier. His retrospective Account of an Anticipation was submitted in 1941, rejected in 1942, and published posthumously in 1965. Thus the claim that he simply refused to submit a priority account is false. His ideas deserve attention together with the qualifications and formal work they still required. Stillwell's scholarly reconstruction

Production rules need an application convention

An original teaching system starts with aab and has a rule aX → Xb, where X stands for the rest of the entire word. The trace is

aab → abb → bbb.

The first match uses X=ab; the next uses X=bb. At bbb the rule is unavailable because the word does not begin with a. Each step removes one leading a and appends one b. This is a specifically defined prefix-rewriting system, not a description of every Post production format.

Contrast this with two rules a→ab and b→ba. Replacing one occurrence at a time differs from replacing all symbols simultaneously. From ab, simultaneous substitution gives abba, while replacing only its first symbol gives abb. A derivation is meaningless unless the rule-selection and replacement conventions are stated.

Production systems connect to formal language study, but a grammar is not itself a parser. A grammar specifies generated strings or structures; a parser seeks a derivation for an input under an algorithm and grammar class. Unrestricted rewriting does not inherit the efficient recognition properties of restricted grammar classes merely because both use arrows.

Worked mechanism: a small Post correspondence instance

The Post correspondence problem gives a finite collection of tile types, each carrying a top string and a bottom string. Ask whether some nonempty finite sequence of tiles makes the concatenated top and bottom equal. Tiles may be reused. Allowing the empty sequence would make every instance trivially positive. The general problem is undecidable. MIT lecture

Here is an original two-tile instance:

Tile	Top	Bottom
1	a	ab
2	ba	a

Choose sequence (1,2). The top is a followed by ba, giving aba. The bottom is ab followed by a, also aba. Neither tile alone works. The first tile leaves an unmatched b on the bottom; the second repairs that imbalance with a suitable continuation.

A systematic search enumerates all length-one sequences, then length-two sequences, and so on. Every candidate is finite and its two concatenations can be compared. Therefore any solution is eventually found. But for a negative instance the search can continue forever. A finite cutoff proves only that no solution occurs below that cutoff.

For an example with a provable negative answer, use the sole tile (a,aa). Repeating it k times produces lengths k and 2k. Equality requires k=0, which is forbidden. This elementary invariant decides that instance. General undecidability does not mean that no individual negative instance can ever be proved negative.

Enumerability, decisions, and levels

A set is computably enumerable if a procedure can recognize its members, possibly failing to halt on nonmembers. Equivalently, its elements can be effectively listed, with conventions accommodating the empty set. Calling every such set the range of a total function without an exception wrongly excludes the empty set.

If both a set and its complement are computably enumerable, run their recognizers in alternating steps. Exactly one must eventually accept any given input, giving a terminating decision procedure. This is why enumeration of only the positive side is weaker than decision. Computability account

In the standard arithmetical hierarchy, Σ⁰₁ sets are computably enumerable, Π⁰₁ sets are their complements, and Δ⁰₁ sets are decidable. Higher levels allow additional alternating unbounded quantifiers. A standard jump characterization says that Σ⁰ₙ₊₁ sets are computably enumerable relative to the nth Turing jump of the empty set. This is a definability hierarchy, not a running-time classification, and not a linear ordering of all Turing degrees. Post's problem asked whether a computably enumerable degree can lie strictly between computable sets and the halting problem; it was answered positively by Muchnik and Friedberg. Hierarchy and degree theory

Exercises

1. For the two-tile instance above, list all four sequences of length two and identify which are solutions. Explain why one successful finite trace proves a yes answer but four failures would not prove a no answer.
2. Prove that the instance with tiles (a,aa) and (b,bb) has no solution. Use an invariant that survives every allowed choice, not a list of examples.
3. Suppose an algorithm recognizes members of A and another recognizes members of its complement. Design a decider. Explain why running the first recognizer to completion before starting the second can fail. Then state the direction of reduction needed to prove another problem X undecidable using PCP.

Compare your reasoning with the worked solutions

1. (1,1) yields top aa and bottom abab; (1,2) yields aba and aba; (2,1) yields baa and aab; (2,2) yields baba and aa. Only (1,2) works among these. Its equality is a complete witness. Failure at length two would leave every longer sequence unexamined, so it could not establish general nonexistence.
2. Every tile contributes one top character and two bottom characters. After any nonempty k-tile sequence, the top has length k and the bottom length 2k. Equal strings must have equal lengths; k=2k forces k=0. This contradicts nonemptiness regardless of which tiles were selected or in what order.
3. Simulate one step of the A recognizer, then one of the complement recognizer, repeatedly. Accept when the first accepts and reject when the second accepts. Membership in exactly one side ensures termination. Sequentially waiting for the first can hang forever when the input lies outside A. For undecidability, construct a computable transformation from PCP instances to X instances preserving yes and no answers. A decider for X would then decide PCP. Reducing X to PCP alone does not establish that X is undecidable.

Source limits

The examples are original finite constructions. The sources establish the historical context and general theorems; they do not warrant invented remarks about how disability shaped proof style or counterfactual claims about whose name a theorem would have carried.