Tag system

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. 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 can be 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()) 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.