Emil Post
Not many people know who Emil Post was, but his model of computational processes as generating systems is one of the simplest to understand. It sits somewhere between the combinator calculus of Curry and Schönfinkel and Church's Lambda Calculus . See Geoffrey K. Pullum's Creation myths of generative grammar and the mathematics of [Chomsky's] Syntactic Structures . Post proved his Normal Form Theorem for Post canonical systems which shows that "Given any Post canonical system on an alphabet A , a Post canonical system in normal form can be constructed from it, possibly enlarging the alphabet, such that the set of words involving only letters of A that are generated by the normal-form system is exactly the set of words generated by the original system" . What this shows is that a Post canonical system which generates a language can be abbreviated by adding non-terminal symbols which allow sub-structures to be reused at multiple places, thus potentially ...