Lag system

A lag system is a Post normal system with similar semantics and structure to tag systems.

The major difference is that while a tag system has a deletion number and rules which operate on the first symbol of the word, lag systems have a prematch number m and rules which match on the first m symbols of the word.

In tuple form, a lag system is a 3-tuple $(\Sigma ,\beta ,L)$:

• A set of symbols $\Sigma$
• A match length $\beta$
• A set of productions $L$, which each $l_{i}\in L$ as $l_{i}:\Sigma ^{\beta }\rightarrow \Sigma ^{\ast }$
  • That is, each rule matches $\beta$ symbols and produces a string of any finite length

We may observe the production lengths as a notable property of a system. Let $\epsilon _{i}$ be the length of the production of $l_{i}$, $\epsilon$ being the maximal $\epsilon _{i}$, and $\epsilon ^{-}$ being the minimal. We may also note $\sigma =|\Sigma |$.

Execution proceeds on a word $w$ by taking the first $\beta$ symbols as the prefix, deleting the first symbol of the word, finding the corresponding rule for the selected prefix, and finally appending the production of that rule to the end of the word. Execution continues until the length of the word is less than $\beta$ or there is no rule for the selected prefix. A halting symbol may be implemented by having no rules which are defined for the halting symbol at the start of the prefix.

Wang proved lag systems Turing complete by reducing Shepherdson-Sturgis (SS) machines into a 2-lag system. Wang provided the following translation scheme:

1. $x_{t}x_{t+1}\rightarrow x_{t+1}$
2. $b_{i}x\rightarrow b_{j}x$
3. $e_{i}b_{j}\rightarrow e_{j}$
4. $xe_{i}\rightarrow 0$

You may note that there are variable indices in this scheme. This is because these are rule forms, rather than explicit rules. For instance, $x_{t}x_{t+1}\rightarrow x_{t+1}$ has four forms, with one form being $01\rightarrow 1$. Any SS machine can be translated into lag by using the forms listed above.

Lag systems are decidable for $\beta =1$, as well as for $\epsilon \leq 1$. In a fully specified lag system, that is one where every $\Sigma ^{\beta }$ has a corresponding production rule, $\epsilon ^{-}\geq 1$ is also decidable, meaning that Turing complete lag systems of this type must contain a rule which produces the empty string.