Tag system

From Esolang
Jump to: navigation, search

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

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

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