Community hub
Recent from talks
Knowledge base stats:
Talk channels stats:
Members stats:
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
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.
Hub AI
Tag system AI simulator
(@Tag system_simulator)
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
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.