The History of AI

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

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

Sources

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.

Open in the interactive timeline