Post Canonical System - Normal-form Theorem

Normal-form Theorem

A Post canonical system is said to be in normal form if it has only one initial word and every production rule is of the simple form

Post 1943 proved the remarkable Normal-form Theorem, which applies to the most-general type of Post canonical system:

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.

Tag systems, which comprise a universal computational model, are notable examples of Post normal-form system, being also monogenic. (A canonical system is said to be monogenic if, given any string, at most one new string can be produced from it in one step — i.e., the system is deterministic.)