World's most popular travel blog for travel bloggers.

, ,
Problem Detail:

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.