Is there an "official" name for this slight variant of the well known Tag System model of computation, and/or has it been used somewhere?

  • a finite alphabet of symbols $\Sigma$
  • a halt symbol $H$
  • an ordered set of production rules: $$P_i: \alpha_i \rightarrow \beta_i, \quad \alpha_i \in \Sigma^+, \beta_i \in \Sigma^* \cup \{H\}$$
  • the input $w$ is a string in $\Sigma^+$

The computation is:

  1. find the first production rule $P_i$ for which $w = \alpha_i v$;
  2. replace $w = \alpha_i v$ with $v\beta_i$ (i.e. delete the prefix $\alpha_i$ and append $\beta_i$)
  3. halt when no production is found or $\beta_i = H$

This model differs from a tag system because 1) $\alpha_i$ is a string and not a single symbol, 2) the number of characters deleted from the prefix is not fixed.

It can easily simulate a $m$-tag system in "real-time" (for every rule $x \rightarrow P(x)$ of the m-tag system add production rules $xv \rightarrow P(x)$, $v \in |\Sigma|^{m-1}$) and therefore it can efficiently simulate a Turing machine.


That's a Post canonical system in normal form, tweaked slightly to incorporate a halt symbol, and to require application of only the first applicable production rule.

  • $\begingroup$ ok, I think that it casn be considered a monogenic Post Canonical system in normal form (plus the halt symbol) $\endgroup$ – Vor Oct 30 '13 at 8:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.