Bi-tag system

A bi-tag system is a type of tag system where there are two disjoint sets of symbols with different semantics.

Neary and Woods present the following definition for the concept:

• Bi-tag system definitions have
  • Two disjoint sets of symbols $A$ and $E$
  • A halting symbol $e_{h}\in E$
  • A set of productions $P$, each being in one of three forms
    • $a_{j}\rightarrow a_{k}$
    • $e_{j}a_{k}\rightarrow a_{l}e_{m}$
    • $e_{j}a_{k}\rightarrow a_{l}a_{m}e_{n}$

The starting word for a bi-tag system has at least one $A$ symbol and exactly one $E$ symbol. A regular expression which matches a valid starting word, with \A being the symbol/character group for the $A$ symbols and \E for the $E$ symbols, is as follows: \A*(\A\E|\E\A)\A*.

Rules are applied like so:

• If the word starts with $e_{h}$ halt
• If the word starts with an $A$ symbol $a_{j}$, then remove it, find the corresponding production rule $a_{j}\rightarrow a_{k}$ and add $a_{k}$ to the end of the word
• If the word starts with an $E$ symbol followed by an $A$, remove them both as $e_{j}a_{k}$ and find the corresponding production rule $e_{j}a_{k}\rightarrow a_{l}e_{m}$ or $e_{j}a_{k}\rightarrow a_{l}a_{m}e_{n}$, and append the production to the end of the word

Note that these rules mean that the word will only ever have exactly one $E$ symbol in it during the entire execution of the system. This means that during execution, if the word starts with an $E$ symbol followed by an $E$ symbol, or the word consists of just a singular $E$ symbol, the machine entered an invalid state at some point.

Neary and Woods proved bi-tag systems Turing complete by providing a method of simulating clockwise Turing machines.