Tag System - Definition

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:

    Beauty, like all other qualities presented to human experience, is relative; and the definition of it becomes unmeaning and useless in proportion to its abstractness. To define beauty not in the most abstract, but in the most concrete terms possible, not to find a universal formula for it, but the formula which expresses most adequately this or that special manifestation of it, is the aim of the true student of aesthetics.
    Walter Pater (1839–1894)

    ... 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)

    I’m beginning to think that the proper definition of “Man” is “an animal that writes letters.”
    Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)