And in a class 4 cellular automaton such as rule 110 one can readily shortcut the process of evolution for at least a limited number of steps in places where there happen to be only a few well-separated localized structures present. … If one views the pattern of behavior as a piece of data, then as we discussed in Chapter 10 regularities in it allow a compressed description to be found. … One way to try to get an idea about this is just to construct patterns

In satisfiability one sets up a collection of rows of black, white and gray squares, then asks whether there exists any sequence of black and white squares that satisfies the constraint that on every row the color of at least one square agrees with the color of the corresponding square in the sequence. … The translation from the Turing machine problem is achieved by representing the behavior of the Turing machine by saying which of a sequence of elementary statements are true about it at each step: whether the head is in one state or another, whether the cell under the head is black or white, and whether the head is at each of the possible positions it can be in.

Although one has the feeling that this involves more human input, it rapidly becomes extremely difficult to tell what has been created on purpose. And so, for example, if one sees a splash of paint it is almost impossible to know without detailed cultural background and context whether it is intended to be purposeful art. … My main conclusion is rather similar to my conclusion about artificial intelligence in Chapter 10 : that the basic issue is not finding systems that perform sophisticated enough computations, but rather finding ones whose details happen to be similar enough to us as humans that we recognize what they do as showing intelligence.

But as a simple idealization one can consider register machines with just two registers—each storing a number of any size—and just two kinds of instructions: "increments" and "decrement-jumps". … Increment instructions are set up just to increase by one the number stored in a particular register. … First, they decrease by one the number in a particular register.

Testing universality [in symbolic systems] One can tell that a symbolic system is universal if one can find expressions that act like the s and κ combinators, so that, for example, for some expression e , e[x][y][z] evolves to x[z][y[z]] .

[Repetition in] 2D cellular automata As expected from the discussion of constraints on page 942 , the problem of finding repeating configurations is much more difficult in two dimensions than in one dimension. Thus for example unlike in 1D there is no guarantee in 2D that among repeating configurations of a particular period there is necessarily one that consists just of a repetitive array of fixed blocks. … Note that if one considers configurations in 2D that consist only of infinitely long stripes, then the problem reduces again to the 1D case.

Digit sequence encryption One can consider using as encrypting sequences the digit sequences of numbers obtained from standard mathematical functions. … But in many cases one can immediately tell how a sequence was made just by globally applying appropriate mathematical functions. Thus, for example, given the digit sequence of √ s one can retrieve the key s just by squaring the number obtained from early digits in the sequence.

Matrices satisfying constraints One can consider for example magic squares, Latin squares (quasigroup multiplication tables), and matrices having the Hadamard property discussed on page 1073 . One can also consider matrices whose powers contain certain patterns.

It turns out that such discrete transitions are fairly rare among one-dimensional cellular automata, but in two and more dimensions A one-dimensional cellular automaton that shows a discrete change in behavior when the properties of its initial conditions are continuously changed.

And this means that if one looks at the total average density of colored cells throughout the system, it must always remain the same. … But what the pictures below suggest is that if one looks only at the overall distribution of density, then these details will become largely irrelevant—so that a given initial distribution of density will always tend to evolve in the same overall way, regardless of what particular arrangement of cells happened to make up that distribution.