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.
Read more about this topic: Tag System
Famous quotes containing the word definition:
“It’s a rare parent who can see his or her child clearly and objectively. At a school board meeting I attended . . . the only definition of a gifted child on which everyone in the audience could agree was “mine.””
—Jane Adams (20th century)
“It is very hard to give a just definition of love. The most we can say of it is this: that in the soul, it is a desire to rule; in the spirit, it is a sympathy; and in the body, it is but a hidden and subtle desire to possess—after many mysteries—what one loves.”
—François, Duc De La Rochefoucauld (1613–1680)
“... we all know the wag’s definition of a philanthropist: a man whose charity increases directly as the square of the distance.”
—George Eliot [Mary Ann (or Marian)