Tag system

Uses your system voice; voice and rate in settings.

Snapshot

≈ 7 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In the theory of computation, a tag system is a deterministic model of computation published by Emil Leon Post in 19431 as a simple form of a 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 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 constant number of symbols from the head, and appends to the tail a symbol-string that depends solely on the first symbol read in this transition. Because all of the indicated operations are performed in a single transition, a tag machine strictly has only one state.

In the theory of computation, a tag system is a deterministic model of computation published by Emil Leon Post in 1943 as a simple form of a 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 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 constant number of symbols from the head, and appends to the tail a symbol-string that depends solely on the first symbol read in this transition. Because all of the indicated operations are performed in a single transition, a tag machine strictly has only one state. 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( )) assigned to the halting symbol is seen below to play no role in computations, but for convenience is taken to be P( ) = . 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. Thus, the system processes the m-symbol head into a tail of variable length, but the generated tail depends solely on the first symbol of the head. 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 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 (described in the historical note below), in which the only halting word is the empty string. 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)

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 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 {a 1 , ..., a n } and corresponding productions {P 1 , ..., P n } is emulated by a cyclic tag system with m*n productions (Q 1 , ..., Q n , -, -, ..., -), where all but the first n productions are the empty string (denoted by ' '). The Q k are encodings of the respective P k , 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): a 1 = 100...00 a 2 = 010...00 . . . a n = 000...01 That is, a k is encoded as a binary string with a in the k th position from the left, and '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.

Notes

References

(Tag systems are introduced on p. 203ff.)

Text derived from https://en.wikipedia.org/w/index.php?oldid=1363281151 under CC BY-SA 4.0; modifications have been made.

References

  1. ↩Wikipedia publication date (×1) · confidence 0.95 https://en.wikipedia.org/w/index.php?oldid=1363281151

Provenance

snapshot enwiki-001363281151 · captured 1783567263.0 · version history

Cite this page as: encyclopegia.org, “Tag system”, snapshot enwiki-001363281151. https://encyclopegia.org/a/tag-system