User:Stkptr/sandbox

Bi-tag systems

A variant of tag systems, known as bi-tag systems, was described by Neary and Woods in their paper on small universal Turing machines. The variant utilizes two disjoint sets of symbols, A and E rather than a single common set of symbols.<ref>

A bi-tag system is described by (A, E, eh, P) where A and E are disjoint sets of symbols (they share no common elements), eh is a halting symbol which is an element of E, and P is the production function which encodes the production rules.

In a normal tag system a production rule is in the form a -> a*, the rule matches a single symbol and produces any number of any kind of symbol at the end of the word. Bi-tag systems are far more restricted, having 3 possible forms for rules. Here, a is any element of A, e is any element of E, both specified by the rule:

a -> a ea -> ae ea -> aae