The pictures below show the largest planar trivalent networks with diameters 1, 2 and 3, and the largest known ones with diameters 4, 5 and 6

The inverse rule, corresponding to multiplication by 1/m , can be obtained by applying the rule for multiplication by the integer k q /m , then shifting right by q positions.

And indeed from the 1950s on, a sequence of special-purpose machines have been built to implement 1D, 2D and sometimes 3D cellular automata.

But as soon as the original equation is nonlinear, say u  m 1 . v + m 2 . v 2 , the situation changes dramatically.

The number of states with spatial period m is given by s[m_, k_]:= k m - Apply[Plus, Map[s[#, k] &, Drop[Divisors[m], -1]]] or equivalently s[m_, k_]:=Apply[Plus, (MoebiusMu[m/#] k # &)[Divisors[m]]] In a cellular automaton with a total of n cells, the maximum possible repetition period is thus s[n, k] .

For in addition to 1/f noise effects, solitons and other collective lattice effects presumably lead to power-law decay of correlations.

In 1982 I noticed that the patterns I had generated with 1D cellular automata looked remarkably similar to patterns on shells.

As a first example—based on a rather simple computation—the picture at the top of the facing page shows a Turing machine set up to add 1 to any number.

Example (h) is the most extreme among 3-state 2-color Turing machines: with the size 7 input 106 it already takes 1,978,213,883 steps

Most often the tests are applied not directly to sequences of 0's and 1's, but instead say to numbers obtained from blocks of 8 elements. A typical collection of tests described by Donald Knuth in 1968 includes: (1) frequency or equidistribution test (possible elements should occur with equal frequency); (2) serial test (pairs of elements should be equally likely to be in descending and ascending order); (3) gap test (runs of elements all greater or less than some fixed value should have lengths that follow a binomial distribution); (4) poker test (blocks corresponding to possible poker hands should occur with appropriate frequencies); (5) coupon collector's test (runs before complete sets of values are found should have lengths that follow a definite distribution); (6) permutation test (in blocks of elements possible orderings of values should occur equally often); (7) runs up test (runs of monotonically increasing elements should have lengths that follow a definite distribution); (8) maximum-of-t test (maximum values in blocks of elements should follow a power-law distribution).