And in d dimensions it is common for it to take, say, t d + 1 steps for one system to emulate t steps of evolution of another. But can it take an exponential number of steps? … A Turing machine can quickly test the highlighted path but could take exponentially long to test all paths.

And unless some digits effectively never matter, this process cannot normally take less steps than there are digits in its input. Indeed, it could in principle be that the process could take a number of steps proportional to the numerical value of its input. … In general, to find the color of a cell after t steps of rule 188 or rule 60 evolution takes about Log[2, t] steps.

Localized structures are visible, but the overall pattern never seems to take on any kind of simple repetitive form.

It takes more than 4000 steps for the final outcome involving 8 separate structures to become clear.

For the initial condition on the bottom right, the system again evolves to a fixed configuration, but now this takes 65,555 steps, and the configuration involves 65,536 opening and closing brackets. … It turns out that this particular system always evolves to a fixed configuration, but for initial conditions of size n can take roughly n iterated powers of 2 (or 2 2 2… ) to do so.

In fact, it turns out that in continuous cellular automata it takes only extremely simple rules to generate behavior of considerable complexity. … A continuous cellular automaton whose rule adds the constant 1/4 to the average gray level for a cell and its immediate neighbors, and takes the fractional part of the result.

What is typically done in practice is to take a sequence that is given and compute from it the values of various specific quantities, and then to compare these values with averages obtained by looking at all possible sequences. … And if one finds that a value computed from a particular sequence lies close to the average for all possible sequences then one can take this as evidence that the sequence is indeed random. But if one finds that the value lies far from the average then one can take this as evidence that the sequence is not random.

In neither case is it clear what the final outcome will be—whether apparent randomness will take over, or whether a simple repetitive form will emerge.

In neither case is it clear what the final outcome will be—whether apparent randomness will take over, or whether a simple repetitive form will emerge.

Even though the system is reversible, this region tends to organize itself so as to take on a much simpler form.