World's most popular travel blog for travel bloggers.

[Answers] Tag system variant

, , No Comments
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.

Asked By : Vor

Answered By : r.e.s.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14034

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback