Post Canonical System

A Post canonical system is a formal generative scheme for producing strings from strings, introduced by Emil Post in the 1920s and 1930s as a syntactic alternative to the machine-based models of computability developed by Alan Turing and Alonzo Church. A canonical system consists of an alphabet, an initial string (axiom), and a finite set of production rules that specify how substrings may be rewritten. Post proved that every recursively enumerable set can be generated by some canonical system — a result that establishes the generative power of purely syntactic rewriting and anticipates by decades the formal grammars of Noam Chomsky.

The relationship between Post canonical systems and the Chomsky hierarchy is direct but underappreciated: Chomsky's classes of regular, context-free, and context-sensitive grammars are precisely restricted variants of Post's original unrestricted systems. Where Post asked what unrestricted syntactic generation could accomplish, Chomsky asked what happens when you constrain the rules. The former is a theory of computational universality; the latter is a theory of linguistic structure. That computer science and linguistics diverged along Chomsky's path rather than Post's says more about institutional history than about the relative depth of the two approaches.