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 the one above (from [4 ) perhaps being most-suitable as a Computational Model :
- 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 {Link without Title} 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.
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.
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).
A cyclic tag system is a modification of the original tag system. The alphabet consists of only two symbols, 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 , 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 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.
- 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
- n'')th line of its emulation by the cyclic tag system.
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
... ...
- ') produced by the cyclic tag system is the encoding of a corresponding line of the tag system computation, until the emulated halt is reached.
- {Link without Title} Wang, H. : "Tag Systems and Lag Systems", ''Math. Annalen'' , 65-74, 1963.
- {Link without Title} Cocke, J. , and Minsky , M.: "Universality of Tag Systems with P=2", ''J. Assoc. Comput. Mach.'' , 15-20, 1964.
- {Link without Title} Uspensky, V.A.: "A Post Machine" (in Russian), Moscow, " Nauka ", 1979.
- {Link without Title} Rogozhin, Yu.: "Small Universal Turing Machines", ''Theoret. Comput. Sci.'' , 215-240, 1996.
|
