Finite Combinatory Processes
Era 1 · The foundations (1763–1942) › Computability
- Lineage
- Symbols and logic
- Kind
- Publication
Who
City College of New York
What happened
Emil Post publishes "Finite Combinatory Processes. Formulation 1" in the Journal of Symbolic Logic: three pages describing a worker who marks boxes by following instructions, a model of computation almost identical to the Turing machine.
Why it mattered
A third independent definition of mechanical calculation, published the same year as Church's and Turing's. Its style, rules that rewrite strings of symbols, reappears in the production systems of symbolic AI.
The full story
Emil Post, born in 1897 in Augustów, in what was then Russian Poland, emigrated to New York as a child. Post's 1920 dissertation had proved that propositional logic is consistent and complete, and during the 1920s Post independently reached ideas close to incompleteness, without publishing them. Post worked as a high school teacher and, from 1936, at the City College of New York.
The 1936 paper runs three pages and opens by placing itself alongside Gödel's theorem and Church's results on unsolvable problems. It describes a space of boxes in a row and a worker who can do only a few things: mark the box it is in, erase it, move to the next box, and check whether a box is marked in order to choose the next instruction. Post proposes that everything that can be calculated by a finite procedure can be calculated this way.
It is almost the same as the Turing machine, which was being published in London in those same months. A note in the paper points this out: it invites comparison with Turing's paper and makes clear that the work was written completely independently.
Post's work then took an independent path. In the 1940s Post studied systems that transform strings of symbols through rewriting rules, and these were used to prove that certain word problems have no solution. That way of describing computation as rules that rewrite symbols is the one taken up by the theory of formal languages and by the rule systems of symbolic AI.
Builds on
The incompleteness theorems (1931), The lambda calculus and an unsolvable problem (April 1936)
Documented direct influence
From its first sentence the paper presents itself as a development in the line of Gödel's incompleteness theorem and Church's unsolvable problems
Leads to
On Computable Numbers (November 30, 1936)
Independent convergence
Two almost identical models of mechanical computation, written separately; a note in Post's paper invites comparison with Turing's and makes clear it was written independently
Threads that pass through here
- From Hilbert's question to the universal machine (step 6 of 7)
Sources
Original source
Scholarship and context
Further reading
How to cite
“Finite Combinatory Processes.” The History of AI, revised November 13, 2026. https://thehistoryofai.com/en/milestone/post-combinatory-processes
This entry was last reviewed on November 13, 2026.