Search NKS | Online
11 - 20 of 42 for Drop
![](/common/images/search/spacer.gif)
One-element-dependence tag systems [emulating TMs]
Writing the rule {3, {{0, _, _} {0, 0}, {1, _, _} {1, 1, 0, 1}}} from page 895 as {3, {0 {0, 0}, 1 {1, 1, 0, 1}}} the evolution of a tag system that depends only on its first element is obtained from
TS1EvolveList[rule_, init_, t_] := NestList[TS1Step[rule, #] &, init, t]
TS1Step[{n_, subs_}, {}] = {}
TS1Step[{n_, subs_}, list_] := Drop[Join[list, First[list] /. subs], n]
Given a Turing machine in the form used on page 888 the following will construct a tag system that emulates it:
TMToTS1[rules_] := {2, Union[Flatten[rules /. … The configuration of the tape on each side of the head in the Turing machine evolution can be obtained from the tag system evolution using
Cases[history, x : {a[_], ___} Apply[{#1, Reverse[#2]} &, Map[ Drop[IntegerDigits[Count[x, #], 2], -1] &, {_b, _d}]]]
Early telephony and sound recording in the late 1800s already used the idea of compressing sounds by dropping high- and low-frequency components.
And in effect, this then means that other nodes are dropped from the network, so that the total size of the network decreases.
Implementation [of tag systems]
With the rules for case (a) on page 94 given for example by
{2, {{0, 0} {1, 1}, {1, 0} {}, {0, 1} {1, 0}, {1, 1} {0, 0, 0}}}
the evolution of a tag system can be obtained from
TSEvolveList[{n_, rule_}, init_, t_] := NestList[If[Length[#] < n, {}, Join[Drop[#, n], Take[#, n] /. rule]]&, init, t]
An alternative implementation is based on applying to the list at each step rules such as
{{0, 0, s___} {s, 1, 1}, {1, 0, s___} {s}, {0, 1, s___} {s, 1, 0}, {1, 1, s___} {s, 0, 0, 0}}
There are a total of ((k r + 1 - 1)/(k - 1)) k n possible rules if blocks up to length r can be added at each step and k colors are allowed.
The system works essentially by dropping vowels and assigning consonants to six possible groups.
If one works directly with a digit sequence of fixed length, dropping any carries on the left, then a repetitive pattern is typically obtained fairly quickly.
For a start, in generating the network of paths one only ever need keep a single path that leads to any particular string; just like in many of my pictures of multiway systems one can in effect always drop any duplicate strings that occur. One might at first imagine that if p and q are both short strings then one could also drop any very long strings that are produced.
Huffman coding
From a list p of probabilities for blocks, the list of codewords can be generated using
Map[Drop[Last[#], -1] &, Sort[ Flatten[MapIndexed[Rule, FixedPoint[Replace[Sort[#], {{p0_, i0_}, {p1_, i1_}, pi___} {{p0 + p1, {i0, i1}}, pi}] & , MapIndexed[List, p]] 〚 1, 2 〛 , {-1}]]]] -1
Given the list of codewords c , the sequence of blocks that occur in encoded data d can be uniquely reconstructed using
First[{{}, d} //.
In its typical form this procedure works by dropping all vowels and grouping together letters like "d" and "t" that sound similar, with the result that at least in some approximation the only features that are kept are ones that make a difference in the way a word sounds.
The idea of arithmetic coding is to represent each such bin by the digit sequence of the shortest number within the bin—after trailing zeros have been dropped.
![](/common/images/search/spacer.gif)