If there are n nodes in such a network, then if any blocks are excluded, the shortest one of them must be of length less than n . And if there are going to be an infinite number of excluded blocks, there must be additional excluded blocks with lengths between n and 2n . In rule 126, the lengths of the shortest newly excluded blocks on successive steps are 0, 3, 12, 13, 14, 14, 17, 15.

Planck length Even in existing particle physics it is generally assumed that the traditional simple continuum description of space must break down at least below about the Planck length Sqrt[ℏ G/c 3 ] ≃ 2 × 10 -35 meters—since at this scale dimensional analysis suggests that quantum effects should be comparable in magnitude to gravitational ones.

For certainly h does not in general give the length of the shortest possible description of the data; all it does is to give the shortest length of description that is obtained by treating successive blocks as if they occur with independent probabilities. With this assumption one then finds that maximal compression occurs if a block of probability p[i] is represented by a codeword of length -Log[2, p[i]] . … For p[i] that are not powers of 1/2, non-integer length codewords would be required.

But even CTToR110[{{0, 0, 0, 0, 0, 0}, {}, {1, 1, 1, 1, 1, 1}, {}}, {1}] already yields blocks of lengths {105736, 34717, 95404} . … The part of the middle block that actually encodes an initial condition grows like 180 Length[init] . The core of the right-hand block grows approximately like 500 (Length[Flatten[rules]] + Length[rules]) , but to make a block that can just be repeated without shifts, between 1 and 30 repeats of this core can be needed.

Cycle lengths [in networks] The lengths of the shortest cycles (girths) of the networks on page 479 are (a) 3, (b) 5, (c) 4, (d) 4, (e) 3, (f) 5, (g) 6, (h) 10, (i) ∞, (j) 3.

Iterated run-length encoding Starting say with {1} consider repeatedly replacing list by (see page 1070 ) Flatten[Map[{Length[#], First[#]} &, Split[list]]] The resulting sequences contain only the numbers 1, 2 and 3, but otherwise at first appear fairly random. … The length of the sequence at the n th step grows like λ n , where λ ≃ 1.3 is the root of a degree 71 polynomial, corresponding to the largest eigenvalue of the transition matrix for the substitution system.

The pictures below show on the left the last rules needed to generate any sequence of each successive length—and on the right the form of the sequence (as well as its continuation after length n ). Since some different rules generate the same sequences (see page 956 ) one needs to go through somewhat more than 2 n rules to get every sequence of length n . The sequences shown below can be thought of as being in a sense the ones of each length that are the most difficult to generate—or have the highest algorithmic information content.

In some respects this scheme is a two-dimensional analog of run-length encoding, and when there are large regions of uniform color it yields significant compression. … Pointers are used only for repeats that are of length at least 4.

With just two possible elements, no sequence above length 3 can satisfy this constraint. … (For example, with k = 2 , {___, x__, y__, x__, y__, ___} always matches any sequence with length more than 18.) … And a potential sign of this would be patterns for which the number of sequences that avoid them varies in a complicated way with length.

Block occurrences [in rule 30] The pictures below show at which step each successive block of length up to 8 first appears in evolution according to various cellular automaton rules starting from a single black cell. For rule 30, the numbers of steps needed for each block of lengths 1 through 10 to appear at least once is {1, 2, 4, 12, 22, 24, 33, 59, 69, 113} .