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:

    Was man made stupid to see his own stupidity?
    Is God by definition indifferent, beyond us all?
    Is the eternal truth man’s fighting soul
    Wherein the Beast ravens in its own avidity?
    Richard Eberhart (b. 1904)

    One definition of man is “an intelligence served by organs.”
    Ralph Waldo Emerson (1803–1882)

    Scientific method is the way to truth, but it affords, even in
    principle, no unique definition of truth. Any so-called pragmatic
    definition of truth is doomed to failure equally.
    Willard Van Orman Quine (b. 1908)