# Tag system

A **tag system** is a restricted kind of Post normal system where productions can only be uniquely selected based on the first symbol of each of their antecedents.

## Contents

## History

Tag systems were studied by Emil Post as early as 1920. The name comes from the children's schoolyard game, *Tag*, with the analogy being that one end of the axiom is "chasing" the other.

## Definition

A tag system can be defined formally as follows:
^{[1]}
^{[2]}
^{[3]}

A tag system is a 3-tuple (m, A, P), where

- m is a positive integer
- A is a finite alphabet of symbols, one of which is a special
*halting symbol* - P is a set of
*production rules*, assigning some word P(x) to each non-halting symbol x in A; a*word*is a finite string on A

The term *m-tag system* (e.g. 2-tag system, etc.) is often used to
emphasise the parameter m.

A *halting word* is a word either that begins with the halting symbol
or whose length is less than m.

A transformation t is defined on the set of non-halting words, such that if x denotes the leftmost symbol of a word S, then t(S) is the result of deleting the leftmost m symbols of S and appending the word P(x) on the right.

A *computation* by a tag system is a finite sequence of words produced
by iterating the t-transformation, starting with an initially given word
and halting when a halting word is produced. (A computation is not
considered to exist unless a halting word is produced by finitely-many
iterations.)

There are various variants of this definition. E.g. Post's original 1943 version applied appending before deleting, giving only the empty string as halting word.

## Example

Tag system m: 2 A: {1,2,3,H} P: 1 --> 3321H 2 --> 331 3 --> 33 Computation Initial word: 211 1331 313321H 3321H33 21H3333 H3333331 (halt).

## Computational class

In 1961, Marvin Minsky^{[4]} gave a method for translating any Turing machine with a given number of symbols into a tag system with a proportional number of symbols, thus showing that tag systems are Turing-complete. Many 2-tag systems have since been proved Turing-complete as well.

## References

- ↑ Wang, H.
*Tag Systems and Lag Systems*, Math. Annalen 152, 65-74 (1963). - ↑ Cocke, J., and Minsky, M.
*Universality of Tag Systems with P=2*, J. Assoc. Comput. Mach. 11, 15-20 (1964). - ↑ Rogozhin, Yu.
*Small Universal Turing Machines*, Theoret. Comput. Sci. 168, 215-240 (1996). - ↑ Minsky, M.
*Recursive Unsolvability of Post's Problem of "Tag" and other Topics in Theory of Turing Machines*, the Annals of Mathematics, 2nd ser., Vol. 74, No. 3. (Nov., 1961), pp. 437–455.

## See also

## External resources

- Tag System on Wikipedia