patternMinor
Tag system variant
Viewed 0 times
systemvarianttag
Problem
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?
$$P_i: \alpha_i \rightarrow \beta_i, \quad \alpha_i \in \Sigma^+, \beta_i \in \Sigma^* \cup \{H\}$$
The computation is:
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.
- 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:
- find the first production rule $P_i$ for which $w = \alpha_i v$;
- replace $w = \alpha_i v$ with $v\beta_i$ (i.e. delete the prefix $\alpha_i$ and append $\beta_i$)
- 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.
Solution
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.
Context
StackExchange Computer Science Q#14034, answer score: 2
Revisions (0)
No revisions yet.