But around 1961 they did systematically study all 4096 2-state 2-color machines, and simulated the behavior of some simple Turing machines on a computer. … As an offshoot of abstract studies of Turing machines, Tibor Radó in 1962 formulated what he called the Busy Beaver Problem: to find a Turing machine with a specified number of states that "keeps busy" for as many steps as possible before finally reaching a particular "halt state" (numbered 0 below). … By 1966 the results for 2, 3 and 4 states had been found: the maximum numbers of steps are 6, 21 and 107, respectively, with 4, 5 and 13 final black cells.

Boole identified 1 with True and 0 with False , then noted that theorems in logic could be stated as equations in which Or is roughly Plus and And is Times —and that such equations can be manipulated by algebraic means. … The "Huntington version" of page 773 was given by Edward Huntington in 1933, along with {( ¬ ¬ a)  a, (a ∨ ¬ (b ∨ ¬ b))  a, ( ¬ ( ¬ (a ∨ ¬ b) ∨ ¬ (a ∨ ¬ c)))  (a ∨ ¬ (b ∨ c))} The "Robbins version" was suggested by Herbert Robbins shortly thereafter, but only finally proved correct in 1996 by William McCune using automated theorem proving (see page 1157 ). … In 1931 Mordechaj Wajsberg found the slightly simpler {(a ⊼ (b ⊼ c)) ⊼ (((d ⊼ c) ⊼ ((a ⊼ d) ⊼ (a ⊼ d))) ⊼ (a ⊼ (a ⊼ b)))} Such an axiom system can be converted to an equational one using Module[{a}, With[{t = a ⊼ (a ⊼ a), i = #1 ⊼ (#2 ⊼ #2) &}, Join[Thread[axioms  t], {i[t ⊼ (b ⊼ c), c]  t, i[t, b]  b, i[i[a, b], b]  i[i[b, a], a]}]]] but then involves 4 axioms.

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). … Of the sequences on page 594 , (a) through (d) as well as (f) fail every single one of the tests, (e) fails only the serial test, while (g) and (h) pass all the tests.

[No text on this page] The behavior of all cellular automata that involve only nearest neighbors in a symmetrical way, have two possible colors for each cell, and leave states consisting only of white cells unchanged.

An example of a generalization is the quantity given for blocks of size n by h[q_, n_]:= Log[k, Sum[p[i] q , {i, k n }]]/(n(q - 1) where q = 0 yields set entropy, the limit q  1 measure entropy, and q = 2 so-called correlation entropy.

In a sense what one needs is a hashing procedure in which the hash codes that are generated depend only on features of the data that really make a difference, and not on others. … And so, as we discussed earlier in this chapter , the human visual system, for example, appears to be based on having nerve cells that respond only to certain specific features of images. And this means that if one looks only at the output from these nerve cells, then one gets a representation of visual images in which two images that differ only in certain kinds of details will be assigned the same representation.

Among the 256 so-called elementary cellular automata that allow only two possible colors for each cell and depend only on nearest neighbors, the only clear immediate example is rule 110—together with rules 124, 137 and 193 obtained by trivially reversing left and right or black and white. … In fact, as illustrated in the pictures on the facing page , it is sufficient in such cases just to use so-called totalistic rules in which the new color of a cell depends only on the average color of cells in its neighborhood, and not on their individual colors. In two dimensions class 4 behavior can occur with rules that involve only two colors and only nearest neighbors—as shown on page 249 .

The position of this cell is chosen entirely at random, with the only constraint being that it should be adjacent to an existing cell in the cluster. … The pictures below, for example, show generalizations of the aggregation model in which new cells are added only at positions that have certain numbers of existing neighbors. And despite such changes Patterns produced by generalized aggregation models in which a new cell is added only if (a) it would have only one immediate neighbor (out of four), or (b) it would have either one or four neighbors.

The pictures at the top above are obtained by keeping only the steps indicated by arrows on the left. … The pictures at the top above are obtained by keeping only the steps indicated by arrows on the left.

But is this in fact the only way to formulate logic? … Nand and Nor are mostly used only in circuit design and in a few foundational studies of logic. … The functions are numbered like 2-neighbor analogs of the cellular automaton rules of page 53 .