# 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.

## 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:   

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 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.