Post production system

views updated

Post production system An approach to effective computability on strings of symbols, formulated by E. L. Post. A Post production is a string rewriting rule. A set L of strings is said to be Post-generable if there exists a finite set of strings, called axioms, and a finite set P of Post productions such that each string in the set can be obtained from the axiom set by some finite derivation, where each step in the derivation is sanctioned by an application of some production in P. It turns out that the class of Post-generable sets on some fixed alphabet A is exactly the class of recursively enumerable sets, order A.