العربية
中国
Français
Deutsch
Ελληνική
हिन्दी
Italiano
日本語
Português
Русский
EspañolTAG SYSTEM
A 'tag system' is a deterministic computational model published by Emil Leon Post in 1943 as a simple form of string rewriting system. A tag system may also be viewed as an abstract machine, called a 'Post tag machine' (not to be confused with Post-Turing machines) -- briefly, a finite state machine whose only tape is a FIFO queue of unbounded length, such that in each transition the machine reads the symbol at the head of the queue, deletes a fixed number of symbols from the head, and may append symbols to the tail.
A ''tag system'' is a triplet (''m'', ''A'', ''P''), where
★ ''m'' is a positive integer, called the ''deletion number''.
★ ''A'' is a finite alphabet of symbols, one of which is a special ''halting symbol''. Finite (possibly empty) strings on ''A'' are called ''words''.
★ ''P'' is a set of ''production rules'', assigning a word ''P(x)'' (called a ''production'') to each symbol ''x'' in ''A''. The production (say ''P(H)'') assigned to the halting symbol is seen below to play no role in computations, but for convenience is taken to be ''P(H)'' = '''H'''.
The term ''m-tag system'' is often used to emphasise the deletion number. Definitions vary somewhat in the literature [1][2][3][4][5], the one presented here being that of Rogozhin[5].
★ 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 particular, Rogozhin [5] established the universality of the class of 2-tag systems with alphabet {''a1'', ..., ''an'', H} and corresponding productions {''ananW1'', ..., ''ananWn-1'', ''anan'', H}, where the ''Wk'' are nonempty words.
The use of a halting symbol in the present definition allows the output of a computation to be encoded in the final word, whereas otherwise the sequence of deleted symbols would be used for that purpose.
The above definition differs from that of Post [1], whose tag systems use no halting symbol, but rather halt only on the empty word, with the tag operation ''t'' being defined as follows:
★ If ''x'' denotes the leftmost symbol of a nonempty word ''S'', then ''t''(''S'') is the operation consisting of first appending the word ''P(x)'' to the right end of ''S'', and then deleting the leftmost ''m'' symbols of the result — deleting all if there be less than ''m'' symbols.
The above remark concerning the Turing-completeness of the set of ''m''-tag systems, for any ''m'' > 1, applies also to these tag systems as originally defined by Post.
According to a footnote in Post's article [1], B. P. Gill suggested the name for an earlier variant of the problem in which the first ''m'' symbols are left untouched, but rather a check mark indicating the current position moves to the right by ''m'' symbols every step. The name for the problem of determining whether or not the check mark ever touches the end of the sequence was then dubbed the "problem of tag", referring to the children's game of tag.
A cyclic tag system is a modification of the original tag system. The alphabet consists of only two symbols, '0' and '1', and the production rules comprise a list of productions considered sequentially, cycling back to the beginning of the list after considering the "last" production on the list. For each production, the leftmost symbol of the word is examined -- if the symbol is '1', the current production is appended to the right end of the word; if the symbol is '0', no characters are appended to the word; in either case, the leftmost symbol is then deleted. The system halts if and when the word becomes empty.
Cyclic tag systems were created by Matthew Cook under the employ of Stephen Wolfram, and were used in Cook's demonstration that the Rule 110 cellular automaton is universal. A key part of the demonstration was that cyclic tag systems can emulate a Turing-complete class of tag systems.
An ''m''-tag system with alphabet {''a1'', ..., ''an''} and corresponding productions {''P1'', ..., ''Pn''} is emulated by a cyclic tag system with ''m
★ n'' productions (''Q1'', ..., ''Qn'', -, -, ..., -), where all but the first ''n'' productions are the empty string (denoted by '-'). The ''Qk'' are encodings of the respective ''Pk'', obtained by replacing each symbol of the tag system alphabet by a length-''n'' binary string as follows (these are to be applied also to the initial word of a tag system computation):
''a1'' = 100...00
''a2'' = 010...00
.
.
.
''an'' = 000...01
That is, ''ak'' is encoded as a binary string with a 1 in the kth position from the left, and 0's elsewhere. Successive lines of a tag system computation will then occur encoded as every (''m
★ n'')th line of its emulation by the cyclic tag system.
This is a very small example to illustrate the emulation technique.
Every sixth line (marked by '
★ ') produced by the cyclic tag system is the encoding of a corresponding line of the tag system computation, until the emulated halt is reached.
★ [1] Post, E.: "Formal reductions of the combinatorial decision problem", ''American Journal of Mathematics'', 65 (2), 197-215 (1943). (Tag systems are introduced on p.203ff.)
★ [2] Wang, H.: "Tag Systems and Lag Systems", ''Math. Annalen'' '152', 65-74, 1963.
★ [3] Cocke, J., and Minsky, M.: "Universality of Tag Systems with P=2", ''J. Assoc. Comput. Mach.'' '11', 15-20, 1964.
★ [4] Uspensky, V.A.: "A Post Machine" (in Russian), Moscow, "Nauka", 1979.
★ [5] Rogozhin, Yu.: "Small Universal Turing Machines", ''Theoret. Comput. Sci.'' '168', 215-240, 1996.
★ http://mathworld.wolfram.com/TagSystem.html
★ http://mathworld.wolfram.com/CyclicTagSystem.html
★ http://www.wolframscience.com/nksonline/page-95 (cyclic tag systems)
★ http://www.wolframscience.com/nksonline/page-669 (emulation of tag systems)
★ C++ Simulator of a Nondeterministic and Deterministic Multitape Post Machine (free software).
★ Bitwise Cyclic Tag (BCT) (a bitwise variant of cyclic tag systems)
| Contents |
| Definition |
| Example |
| Historical note on the definition of tag system |
| Origin of the name "tag" |
| Cyclic Tag Systems |
| Example |
| Emulation of tag systems by cyclic tag systems |
| Example |
| References |
| External links |
Definition
A ''tag system'' is a triplet (''m'', ''A'', ''P''), where
★ ''m'' is a positive integer, called the ''deletion number''.
★ ''A'' is a finite alphabet of symbols, one of which is a special ''halting symbol''. Finite (possibly empty) strings on ''A'' are called ''words''.
★ ''P'' is a set of ''production rules'', assigning a word ''P(x)'' (called a ''production'') to each symbol ''x'' in ''A''. The production (say ''P(H)'') assigned to the halting symbol is seen below to play no role in computations, but for convenience is taken to be ''P(H)'' = '''H'''.
The term ''m-tag system'' is often used to emphasise the deletion number. Definitions vary somewhat in the literature [1][2][3][4][5], the one presented here being that of Rogozhin[5].
★ 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 particular, Rogozhin [5] established the universality of the class of 2-tag systems with alphabet {''a1'', ..., ''an'', H} and corresponding productions {''ananW1'', ..., ''ananWn-1'', ''anan'', H}, where the ''Wk'' are nonempty words.
The use of a halting symbol in the present definition allows the output of a computation to be encoded in the final word, whereas otherwise the sequence of deleted symbols would be used for that purpose.
Example
2-tag system
Alphabet: {a,b,c,H}
Production rules:
a --> ccbaH
b --> cca
c --> cc
Computation
Initial word: baa
acca
caccbaH
ccbaHcc
baHcccc
Hcccccca (halt).
Historical note on the definition of tag system
The above definition differs from that of Post [1], whose tag systems use no halting symbol, but rather halt only on the empty word, with the tag operation ''t'' being defined as follows:
★ If ''x'' denotes the leftmost symbol of a nonempty word ''S'', then ''t''(''S'') is the operation consisting of first appending the word ''P(x)'' to the right end of ''S'', and then deleting the leftmost ''m'' symbols of the result — deleting all if there be less than ''m'' symbols.
The above remark concerning the Turing-completeness of the set of ''m''-tag systems, for any ''m'' > 1, applies also to these tag systems as originally defined by Post.
Origin of the name "tag"
According to a footnote in Post's article [1], B. P. Gill suggested the name for an earlier variant of the problem in which the first ''m'' symbols are left untouched, but rather a check mark indicating the current position moves to the right by ''m'' symbols every step. The name for the problem of determining whether or not the check mark ever touches the end of the sequence was then dubbed the "problem of tag", referring to the children's game of tag.
Cyclic Tag Systems
A cyclic tag system is a modification of the original tag system. The alphabet consists of only two symbols, '0' and '1', and the production rules comprise a list of productions considered sequentially, cycling back to the beginning of the list after considering the "last" production on the list. For each production, the leftmost symbol of the word is examined -- if the symbol is '1', the current production is appended to the right end of the word; if the symbol is '0', no characters are appended to the word; in either case, the leftmost symbol is then deleted. The system halts if and when the word becomes empty.
Example
Cyclic Tag System
Productions: (010, 000, 1111)
Computation
Initial Word: 11001
Production Word
---------- --------------
010 11001
000 1001010
1111 001010000
010 01010000
000 1010000
1111 010000000
010 10000000
. .
. .
Cyclic tag systems were created by Matthew Cook under the employ of Stephen Wolfram, and were used in Cook's demonstration that the Rule 110 cellular automaton is universal. A key part of the demonstration was that cyclic tag systems can emulate a Turing-complete class of tag systems.
Emulation of tag systems by cyclic tag systems
An ''m''-tag system with alphabet {''a1'', ..., ''an''} and corresponding productions {''P1'', ..., ''Pn''} is emulated by a cyclic tag system with ''m
★ n'' productions (''Q1'', ..., ''Qn'', -, -, ..., -), where all but the first ''n'' productions are the empty string (denoted by '-'). The ''Qk'' are encodings of the respective ''Pk'', obtained by replacing each symbol of the tag system alphabet by a length-''n'' binary string as follows (these are to be applied also to the initial word of a tag system computation):
''a1'' = 100...00
''a2'' = 010...00
.
.
.
''an'' = 000...01
That is, ''ak'' is encoded as a binary string with a 1 in the kth position from the left, and 0's elsewhere. Successive lines of a tag system computation will then occur encoded as every (''m
★ n'')th line of its emulation by the cyclic tag system.
Example
This is a very small example to illustrate the emulation technique.
2-tag system
Production rules: (a --> bb, b --> abH, H --> H)
Alphabet encoding: a = 100, b = 010, H = 001
Production encodings: (bb = 010 010, abH = 100 010 001, H = 001)
Cyclic tag system
Productions: (010 010, 100 010 001, 001, -, -, -)
Tag system computation
Initial word: ba
abH
Hbb (halt)
Cyclic tag system computation
Initial word: 010 100 (=ba)
Production Word
---------- -------------------------------
★ 010 010 010 100 (=ba)
100 010 001 10 100
001 0 100 100 010 001
- 100 100 010 001
- 00 100 010 001
- 0 100 010 001
★ 010 010 100 010 001 (=abH)
100 010 001 00 010 001 010 010
001 0 010 001 010 010
- 010 001 010 010
- 10 001 010 010
- 0 001 010 010
★ 010 010 emulated halt --> 001 010 010 (=Hbb)
100 010 001 01 010 010
001 1 010 010
- 010 010 001
... ...
Every sixth line (marked by '
★ ') produced by the cyclic tag system is the encoding of a corresponding line of the tag system computation, until the emulated halt is reached.
References
★ [1] Post, E.: "Formal reductions of the combinatorial decision problem", ''American Journal of Mathematics'', 65 (2), 197-215 (1943). (Tag systems are introduced on p.203ff.)
★ [2] Wang, H.: "Tag Systems and Lag Systems", ''Math. Annalen'' '152', 65-74, 1963.
★ [3] Cocke, J., and Minsky, M.: "Universality of Tag Systems with P=2", ''J. Assoc. Comput. Mach.'' '11', 15-20, 1964.
★ [4] Uspensky, V.A.: "A Post Machine" (in Russian), Moscow, "Nauka", 1979.
★ [5] Rogozhin, Yu.: "Small Universal Turing Machines", ''Theoret. Comput. Sci.'' '168', 215-240, 1996.
External links
★ http://mathworld.wolfram.com/TagSystem.html
★ http://mathworld.wolfram.com/CyclicTagSystem.html
★ http://www.wolframscience.com/nksonline/page-95 (cyclic tag systems)
★ http://www.wolframscience.com/nksonline/page-669 (emulation of tag systems)
★ C++ Simulator of a Nondeterministic and Deterministic Multitape Post Machine (free software).
★ Bitwise Cyclic Tag (BCT) (a bitwise variant of cyclic tag systems)
This article provided by Wikipedia. To edit the contents of this article, click here for original source.
psst.. try this: add to faves
