In Turing machine (f) the maximum number of steps increases exponentially with the length of the input. … But if one ignores inputs where this happens, then at least in examples (i) and (j) the maximum number of steps still grows in a very systematic linear way with the length of the input. … But once again the maximum number of steps in the end just increases like the square of the length of the input.

. • (b) All strings of length n containing exactly one black cell are produced—after at most 2n - 1 steps. • (c) All strings containing even-length runs of white cells are produced. • (d) The set of strings produced is complicated. The last length 4 string produced is , after 16 steps; the last length 6 one is , after 26 steps. • (e) All strings that begin with a black element are produced. • (f) All strings that end with a white element but contain at least one black element, or consist of all white elements ending with black, are produced. Strings of length n take n steps to produce. • (g) The same strings as in (f) are produced, but now a string of length n with m black elements takes n + m - 1 steps. • (h) All strings appear in which the first run of black elements is of length 1; a string of length n with m black elements appears after n + m - 1 steps. • (i) All strings containing an odd number of black elements are produced; a string of length n with m black cells occurs at step n + m - 1 . • (j) All strings that end with a black element are produced. • (k) Above length 1, the strings produced are exactly those starting with a white element.

Run-length encoding Data can be converted to run lengths by Map[Length, Split[data]] . … With completely random input, the output will on average be longer by a factor Sum[2 -(n + 1) r[n], {n, 1, ∞ }] where r[n] is the length of the representation for n .

But for run-length encoding it turns out that ordinary base 2 digit sequences do not quite work. For if the numbers corresponding to the lengths of successive runs are given one after another then there is no way to tell where the digits of one number end and the next begin. … Examples of run-length encoding.

After t steps the maximum conceivable DNF would be of length 2 2t . … The distributions of lengths for all elementary rules are shown below. Note that the length of a minimal DNF representation cannot be considered a reliable measure of the complexity of a function, since among other things, just exchanging the role of black and white can substantially change this length (as in the case of rule 126 versus rule 129).

In each case single cells are encoded as blocks of cells, and all distinct such encodings with blocks up to length 20 are shown.

And in general it is fairly easy to see that in any sequence that is purely repetitive there must beyond a certain length be many blocks whose frequencies are far from equal. … In each case the frequency of a particular block is represented by gray level, with results for blocks of successively greater lengths being shown on successive rows as indicated on the bottom left. … (Note that these substitution systems are the simplest ones that yield equal frequencies of all blocks up to lengths 1, 2 and 3 respectively.)

Pointer-based encoding One can encode a list of data d by generating pointers to the longest and most recent copies of each subsequence of length at least b using PEncode[d_, b_ : 4] := Module[{i, a, u, v}, i = 2; a = {First[d]}; While[i ≤ Length[d], {u, v} = Last[Sort[Table[{MatchLength[d, i, j], j}, {j, i - 1}]]]; If[u ≥ b, AppendTo[a, p[i - v, u]]; i += u, AppendTo[a, d 〚 i 〛 ]; i++]]; a] MatchLength[d_, i_, j_] := With[{m = Length[d] - i}, Catch[ Do[If[d 〚 i + k 〛 =!… The encoded version of a purely repetitive sequence of length n has a length that grows like Log[n] . … The overall fraction of a length n input that consists of repeats of length at least b is greater than 1 - 2 b /n and is essentially 1 - Sum[(1 - 2 -b ) i Product[1 + (1 - 2 -b ) j - (1 - 2 -b - 1 ) j , {j, i - b + 1, i - 1}], {i, b, n - b}]/(n - 2b + 1)

String overlaps The total numbers of strings with length n and k colors that cannot overlap themselves are given by a[0] = 1; a[n_] := k a[n - 1] - If[EvenQ[n], a[n/2], 0] Up to reversal and interchange of A and B , the first few overlap-free strings with 2 colors are A , AB , AAB , AAAB , AABB . The shortest pairs of strings of 2 elements with no self- or mutual overlaps are {"A", "B"} , {"AABB", "AABAB"} , {"AABB", "ABABB"} ; there are a total of 13 such pairs with strings up to length 5, and 85 with strings up to length 6. … There are a total of 36 such triples with no string having length more than 6.

For any input x one can test whether the machine will ever halt using u[{Reverse[IntegerDigits[x, 2]], 0}] u[list_] := v[Split[Flatten[list]]] v[{a_, b_: {}, c_: {}, d_: {}, e_: {}, f_: {}, g___}] := Which[a == {1} || First[a]  0, True, c  {}, False, EvenQ[Length[b]], u[{a, 1 - b, c, d, e, f, g}], EvenQ[Length[c]], u[{a, 1 - b, c, 1, Rest[d], e, f, g, 0}], e  {} || Length[d] ≥ Length[b] + Length[a] - 2, True, EvenQ[Length[e]], u[{a, b , c, d, f, g}], True, u[{a, 1 - b, c, 1 - d, e, 1, Rest[f], g, 0}]] This test takes at most n/3 recursive steps, even though the original machine can take of order n 2 steps to halt.