Post Production Systems

A Post production system is a set of rules, each of which says: if the current string of symbols matches this pattern, replace it with that string. Strip away the meaning, reduce any system of inference to its bare mechanism, and this—Emil Post showed in the 1920s—is what remains. He called the result a production system, proved his normal form theorem (that any such system can be reduced to a single axiom and rules that merely delete a prefix and append a suffix), and established that from this one operation, all of mathematics can in principle be generated. The concept became the taproot of symbolic AI: every expert system of the 1970s and 1980s was a Post production system with handwritten rules; Noam Chomsky’s hierarchy of formal grammars is built on Post-style productions; every compiler that parses a programming language is applying Post’s formalism. The concept also becomes, on inspection, the architecture of large language models: a transformer takes a