Abstract

The idea for the production-based design for computing came originally from writings of Post (1943), who proposed a production rule model as a formal theory of computation. The main construct of this theory was a set of rewrite rules for strings. It is also closely related to the approach taken by Markov algorithms (Markov 1954) and, like them, is equivalent in power to a universal Turing machine.