Tag system
Encyclopedia
A tag system is a deterministic computational model
published by Emil Leon Post
in 1943 as a simple form of Post canonical system
. A tag system may also be viewed as an abstract machine, called a Post tag machine (not to be confused with Post-Turing machine
s)—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 to the tail appends a symbol-string preassigned to the deleted symbol. (Because all of the indicated operations are performed in each transition, a tag machine strictly has only one state.)
The term m-tag system is often used to emphasise the deletion number. Definitions vary somewhat in the literature (cf References), the one presented here being that of Rogozhin.
The use of a halting symbol in the above definition allows the output of a computation to be encoded in the final word alone, whereas otherwise the output would be encoded in the entire sequence of words produced by iterating the tag operation.
A common alternative definition uses no halting symbol and treats all words of length less than m as halting words. Another definition is the original one used by Post 1943 (described in the historical note below), in which the only halting word is the empty string.
.
In the original Collatz sequence, the successor of n is either n/2 (for even n) or 3n + 1 (for odd n). The value 3n + 1 is clearly even for odd n, hence the next term after 3n + 1 is surely (3n + 1)/2. In the sequence computed by the tag system below we skip this intermediate step, hence the successor of n is (3n + 1)/2 for odd n.
In this tag system, a positive integer n is represented by the word aa...a with n a's.
, as was done by Wang 1963 and by Cocke & Minsky 1964.
Conversely, a Turing machine can be shown to be a Universal Turing Machine by proving that it can simulate a Turing-complete class of m-tag systems. For example, Rogozhin 1996 proved 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; he then proved the universality of a very small (4-state, 6-symbol) Turing machine by showing that it can simulate this class of tag systems.
is among the simplest, most-easily described undecidable
decision problem
s:
Given an arbitrary positive integer n and a list of n+1 arbitrary words P1,P2,...,Pn,Q on the alphabet {1,2,...,n}, does repeated application of the tag operation t: ijX → XPi eventually convert Q into a word of length less than 2? That is, does the sequence Q, t1(Q), t2(Q), t3(Q), ... terminate?
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.
.
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.
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.
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.
Computation
Computation is defined as any type of calculation. Also defined as use of computer technology in Information processing.Computation is a process following a well-defined model understood and expressed in an algorithm, protocol, network topology, etc...
published by Emil Leon Post
Emil Leon Post
Emil Leon Post was a mathematician and logician. He is best known for his work in the field that eventually became known as computability theory.-Early work:...
in 1943 as a simple form of Post canonical system
Post canonical system
A Post canonical system, as created by Emil Post, is a string-manipulation system that starts with finitely-many strings and repeatedly transforms them by applying a finite set of specified rules of a certain form, thus generating a formal language...
. A tag system may also be viewed as an abstract machine, called a Post tag machine (not to be confused with Post-Turing machine
Post-Turing machine
A Post–Turing machine is a "program formulation" of an especially simple type of Turing machine, comprising a variant of Emil Post's Turing-equivalent model of computation described below. A Post–Turing machine is a "program formulation" of an especially simple type of Turing machine, comprising a...
s)—briefly, a finite state machine
Finite state machine
A finite-state machine or finite-state automaton , or simply a state machine, is a mathematical model used to design computer programs and digital logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states...
whose only tape is a FIFO
FIFO
FIFO is an acronym for First In, First Out, an abstraction related to ways of organizing and manipulation of data relative to time and prioritization...
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 to the tail appends a symbol-string preassigned to the deleted symbol. (Because all of the indicated operations are performed in each transition, a tag machine strictly has only one state.)
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. All 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 (cf References), the one presented here being that of Rogozhin.
- A halting word is a word that either begins with the halting symbol or whose length is less than m.
- A transformation t (called the tag operation) 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. (By this definition, a computation is not considered to exist unless a halting word is produced in finitely-many iterations. Alternative definitions allow nonhalting computations, for example by using a special subset of the alphabet to identify words that encode output.)
The use of a halting symbol in the above definition allows the output of a computation to be encoded in the final word alone, whereas otherwise the output would be encoded in the entire sequence of words produced by iterating the tag operation.
A common alternative definition uses no halting symbol and treats all words of length less than m as halting words. Another definition is the original one used by Post 1943 (described in the historical note below), in which the only halting word is the empty string.
Example: A simple 2-tag illustration
This is merely to illustrate a simple 2-tag system that uses a halting symbol.
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).
Example: Computation of Collatz sequences
This simple 2-tag system is adapted from [De Mol, 2008]. It uses no halting symbol, but halts on any word of length less than 2, and computes a slightly modified version of the Collatz sequenceCollatz conjecture
The Collatz conjecture is a conjecture in mathematics named after Lothar Collatz, who first proposed it in 1937. The conjecture is also known as the 3n + 1 conjecture, the Ulam conjecture , Kakutani's problem , the Thwaites conjecture , Hasse's algorithm The Collatz conjecture is a...
.
In the original Collatz sequence, the successor of n is either n/2 (for even n) or 3n + 1 (for odd n). The value 3n + 1 is clearly even for odd n, hence the next term after 3n + 1 is surely (3n + 1)/2. In the sequence computed by the tag system below we skip this intermediate step, hence the successor of n is (3n + 1)/2 for odd n.
In this tag system, a positive integer n is represented by the word aa...a with n a's.
2-tag system
Alphabet: {a,b,c}
Production rules:
a --> bc
b --> a
c --> aaa
Computation
Initial word: aaa <--> n=3
abc
cbc
caaa
aaaaa <--> 5
aaabc
abcbc
cbcbc
cbcaaa
caaaaaa
aaaaaaaa <--> 8
aaaaaabc
aaaabcbc
aabcbcbc
bcbcbcbc
bcbcbca
bcbcaa
bcaaa
aaaa <--> 4
aabc
bcbc
bca
aa <--> 2
bc
a <--> 1
(halt)
Turing-completeness of m-tag systems
For each m > 1, the set of m-tag systems is Turing-complete; i.e., for each m> 1, it is the case that for any given Turing machine T, there is an m-tag system that simulates T. In particular, a 2-tag system can be constructed to simulate a Universal Turing machineUniversal Turing machine
In computer science, a universal Turing machine is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input. The universal machine essentially achieves this by reading both the description of the machine to be simulated as well as the input thereof from its own tape. Alan...
, as was done by Wang 1963 and by Cocke & Minsky 1964.
Conversely, a Turing machine can be shown to be a Universal Turing Machine by proving that it can simulate a Turing-complete class of m-tag systems. For example, Rogozhin 1996 proved 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; he then proved the universality of a very small (4-state, 6-symbol) Turing machine by showing that it can simulate this class of tag systems.
The 2-tag halting problem
This version of the halting problemHalting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
is among the simplest, most-easily described undecidable
Undecidable problem
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer....
decision problem
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
s:
Given an arbitrary positive integer n and a list of n+1 arbitrary words P1,P2,...,Pn,Q on the alphabet {1,2,...,n}, does repeated application of the tag operation t: ijX → XPi eventually convert Q into a word of length less than 2? That is, does the sequence Q, t1(Q), t2(Q), t3(Q), ... terminate?
Historical note on the definition of tag system
The above definition differs from that of Post 1943, 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 1943, 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 tagTag (game)
Tag is a playground game played worldwide that involves one or more players chasing other players in an attempt to tag or touch them, usually with their fingers. There are many variations...
.
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
Matthew Cook
Matthew Cook is a mathematician and computer scientist who proved Stephen Wolfram's conjecture that the Rule 110 cellular automaton is Turing-complete. Rule 110 is arguably the simplest Turing-complete system currently known....
under the employ of Stephen Wolfram
Stephen Wolfram
Stephen Wolfram is a British scientist and the chief designer of the Mathematica software application and the Wolfram Alpha computational knowledge engine.- Biography :...
, and were used in Cook's demonstration that the Rule 110 cellular automaton
Rule 110 cellular automaton
The Rule 110 cellular automaton is an elementary cellular automaton with the following rule table:In the table above, when the sequence of 1s and 0s corresponding to the new states is regarded as a binary number, the decimal equivalent is 110; hence the name of the rule.-History:Around 2000,...
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.
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)