Definition

A tag system is a triplet (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 is often used to emphasise the parameter m. Definitions vary somewhat in the literature [1][2][3], the one above (from [3]) perhaps being most-suitable as a computational model: Computation can be defined as finding a solution to a problem from given inputs by means of an algorithm. ...

• A halting word is a word that either 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 transformation t, 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 in finitely-many iterations.)

For each m > 1, the set of m-tag systems is Turing-complete. In computability theory a programming language or any other logical system is called Turing-complete if it has a computational power equivalent to a universal Turing machine. ...

Note that unlike some alternative definitions of tag systems, the present one is such that the "output" of a computation may be encoded in the final 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). 

References

• [1] Wang, H.: "Tag Systems and Lag Systems", Math. Annalen 152, 65-74, 1963.
• [2] Cocke, J., and Minsky, M.: "Universality of Tag Systems with P=2", J. Assoc. Comput. Mach. 11, 15-20, 1964.
• [3] Rogozhin, Yu.: "Small Universal Turing Machines", Theoret. Comput. Sci. 168, 215-240, 1996.

External link

• http://mathworld.wolfram.com/TagSystem.html