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: [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
- A tag system interpreter in Jelly, runnable online at Try It Online! – uses 1-based state numbering, a halt state is specified by giving it the production
[0]