Emil Post's tag system as a demand rate ugen.
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
deletion number. Number of symbols that are deleted at each step.
the string to start with - use integers from 0 to N, which correspond to rule indices.
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).
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).
this parameter decides in what case to apply the above recycle parameter. If recycle = 0, only mode 4 makes a difference.
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.
is written as
[[0, 0], [1, 1, 0, 1]]
is written as
[[0, 2], [1, 1, 0, 1], [0, 1]]
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 .
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'" .
More poetically, looking out for complex messages hidden in noise: Stanislav Lem, His Master's Voice, 1968.
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).
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 .
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 )