Dtag:
Filter:
sc3-plugins/Classes (extension) | UGens > Demand

Dtag
ExtensionExtension

demand rate tag system

Description

Emil Post's tag system as a demand rate ugen.

Class Methods

.new

Arguments:

bufsize

maximum string size - when this size is reached, the process ends (dependent on mode). Theoretically, tag systems have an infinite "tape" (memory) size - practically, one may want to try different finite sizes. This value is static. For a version that runs on a separate buffer, see DbufTag

v

deletion number. Number of symbols that are deleted at each step.

axiom

the string to start with - use integers from 0 to N, which correspond to rule indices.

rules

the production rules are given as an array of arrays. For each integer the production rule at that position is chosen (see rule schema below).

recycle

if this is not zero, the tag system simply adds this value as an offset to its write position and continues where it normally would end. This results in a recycling tag system (see below).

mode

this parameter decides in what case to apply the above recycle parameter. If recycle = 0, only mode 4 makes a difference.

mode 0both recycle when string overrun or string empty (default case)
mode 1recycle only when string overrun, halt when empty
mode 2recycle only when string empty, halt when overrun
mode 3always halt
mode 4always halt and post information.
mode 5same, but post buffer values (max 32) and rule number.

Examples

Inputs and outputs

Most inputs, also rule values, may themselves be demand rate ugens, or any other ugen or value. Thus, while the rule sizes stay the same, the rule values may dynamically changed. If those values are demand rate ugens, the rule values and the deletion number are evaluated each cycle, recycle is called each time the system ends.

At each step, Dtag outputs the tagged symbol, which is the rule index for the next step. If the appended string is needed instead, this can be done by applying the method allSymbols to the UGen.

Rule schema

is written as [[0, 0], [1, 1, 0, 1]]

is written as [[0, 2], [1, 1, 0, 1], [0, 1]]

Emil Post's tag systems

Emil Post developed tag systems from the 1920s onward as an instrument of generalization of symbolic logic, hoping that it would allow the study of properties like decidability and completeness. Due to their intractibility he gave up the attempt to prove their unsolvability. Minsky showed later that tag systems are recursively unsolvable, i.e. of equivalent to a universal turing machine [2].

This type of rewriting system consists of an initial string of symbols (axiom), a set of rules and a deletion number (v). In our implementation, Post's parameter u (size of the alphabet) is implicit is the number of letters in the alphabet used. The deletion number is a very interesting parameter, since it determines what part of the string forms the instructions for the process and what part is omitted. Post described three classes of behaviour: termination, periodicity, and divergence. "The classes with u = 1 or v = 1 or v = u = 2 were proven solvable. The case with u = 2, v > 2 he calls intractable, while he terms the cases u > 2, v = 2 as being of 'bewildering complexity'" [4].

Further reading

More poetically, looking out for complex messages hidden in noise: Stanislav Lem, His Master's Voice, 1968.

How it works

In the beginning, the string is the axiom, and its first symbol is tagged. At each step, the rule is looked up that corresponds to this tagged symbol: 1 corresponds to the rule with index 1 (the 2nd), 0 corresponds to the rule with index 0 (the 1st) etc.

If no rule is found, the process halts. Otherwise, two things happen:

When the string is empty (i.e. the tag has reached its rightmost end), or the maximum memory size is reached, the process halts. When you set mode to 4, this information is posted (be careful, because posting at very high frequencies can overload the system).

Recycling tag systems: a variant of tag systems

Like in an early procedure by Emil Post, in this implementation the symbols are not deleted from the end, but the reading position is advanced (the tag is moved forward). Mathew Cook developed a variant, where instead of a single axiom, one has a list of axioms that is used one after the other [3].

Instead of assuming an infinite tape or such an axiom list, one now can try and see what happens if one assumes a cyclic tape instead - while this may not add any expressive power to the concept, it is an interesting special case. At the loop point (a certain limit string size), a new axiom is chosen from the beginning (r > 0), or backward, from the end of the tape (r < 0).

If recycle is not 0, instead of halting, the old string is reused by cutting out an axiom of that length from the current position and the process continues. For r > 0 the read position is advanced by r steps, for r < 0 the tag is moved back by r steps. If mode = 1, recycling happens only when the string is too large. If mode = 2, recycling happens happens only when the string is empty. (see above)

In the metaphor of the tag game, the recycle parameter ( r ) is the head start for the runaway writer before the tagger (see: http://en.wikipedia.org/wiki/Tag_%28game%29 )