Properties [of cyclic tag systems] Assuming that black and white elements occur in an uncorrelated way, then the sequences in a cyclic tag system with n blocks should grow by an average of Count[Flatten[rules], 1]/n - 1 elements at each step. With n = 2 blocks, this means that growth can occur only if the total number of black elements in both blocks is more than 3. … Note that if all blocks in a cyclic tag system with n blocks have lengths divisible by n , then one can tell in advance on which steps blocks will be added, and the overall behavior obtained must correspond to a neighbor-independent substitution system.

The blocks needed to represent each cell are now larger, since they must include all 32 cases in the rule. … The idea is that each cell in the three-color cellular automaton is represented by a block of three cells in the two-color cellular automaton. And by looking at neighbors out to distance five on each side, the two-color cellular automaton can update these blocks at each step in direct correspondence with the rules of the three-color cellular automaton.

The largest structure in the picture below starts from a block that is 30 cells wide. And with the more than ten billion blocks between 30 and 34 cells wide, no new structures at all appear.

And as the first set of pictures below illustrates, nested patterns are generated very directly in substitution systems by each element successively splitting explicitly into blocks of smaller and smaller elements. … Nesting in one- and two-dimensional neighbor-independent substitution systems in which each element breaks into a block of smaller elements at each step.

Another generalization is to allow blocks at a variety of angles (see above ). … But often it does allow the emulations to work with smaller blocks. … The block-based encodings discussed so far here correspond to block codes.

Arithmetic coding Consider dividing the interval from 0 to 1 into a succession of bins, with each bin having a width equal to the probability for some sequence of blocks to occur. … For any sequence s this can be done using Module[{c, m = 0}, Map[c[#] = {m, m += Count[s, #]/Length[s]} &, Union[s]]; Function[x, (First[RealDigits[2 # Ceiling[2 -# Min[x]], 2, -#, -1]] &)[Floor[Log[2, Max[x] - Min[x]]]]][ Fold[(Max[#1] - Min[#1]) c[#2] + Min[#1] &, {0, 1}, s]]] Huffman coding of a sequence containing a single 0 block together with n 1 blocks will yield output of length about n ; arithmetic coding will yield length about Log[n] . Compression in arithmetic coding still relies, however, on unequal block probabilities, just like in Huffman coding.

The picture shows the evolution of five cells according to the rule shown, with each cell now being represented by a block of 70 cells in the universal cellular automaton.

The basic idea is to represent each cell in the three-color rule by a block of three cells in the two-color rule, according to the correspondence given on the left.

More general conserved quantities Some rules conserve not total numbers of cells with given colors, but rather total numbers of blocks of cells with given forms—or combinations of these. … Rules that show complicated behavior usually do not seem to have conserved quantities, and this is true for example of rules 30, 90 and 110, at least up to blocks of length 10. … For block size b , k b - 1 lists will always appear as a result of trivial conserved quantities.

Tag systems [for rule 110] The discussion in the main text and the construction above require a cyclic tag system with blocks that are a multiple of 6 long, and in which at least one block is added at some point in each complete cycle.