Таг жүйелері және Туринг толықтығы

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.

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 emulates T. In particular, a 2 tag system can be constructed to emulate a Universal Turing machine, as was done by and by
Conversely, a Turing machine can be shown to be a Universal Turing Machine by proving that it can emulate a Turing complete class of m tag systems. For example, proved the universality of the class of 2 tag systems with alphabet {a1, , an, } and corresponding productions {ananW1, , ananWn 1, anan, }, 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 system is an efficient simulator of universal Turing machines, in time. That is, if is a deterministic single tape Turing machine that runs in time , then there is a 2 tag system that simulates it in time.

According to a footnote in , 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.

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 in the kth 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.