Pattern (a) dies out after 36 steps; pattern (b) takes 1017 steps. … Whether a pattern in a cellular automaton ever dies out can be viewed as analogous to a version of the halting problem for Turing machines.

And if one asks whether any initial conditions exist that lead, for example, to a pattern that does not die out, then this too will in general be undecidable—though in a sense this is just an immediate consequence of the fact that given a particular initial condition one cannot tell whether or not the pattern it produces will ever die out. … For if any sequence is going to satisfy the constraint one can show that there must already be a sequence of limited length that does so—and if necessary one can find this sequence by explicitly looking at all possibilities. … And in fact I strongly suspect that even with just three pairs there is already computational irreducibility, so that in effect the only way to answer the question of whether the constraints can be satisfied is explicitly to trace through some fraction of all arbitrarily long sequences—making this question in general undecidable.

And inside the pattern parts begin to die out. … For all but code 1599, the fate of these patterns in fact becomes clear after less than 100 steps.

dies out. … And only after 1017 steps does it finally become clear that the pattern in fact dies out. … After a million steps neither has died out; in fact they are respectively 31,000 and 39,718 cells wide.

Researchers seeking further information should consult the website for the book.

Rule 22—like rule 90 from page 26 —gives a pattern with fractal dimension Log[2,3] ≃ 1.58 ; rule 150 gives one with fractal dimension Log[2, 1+Sqrt[5]] ≃ 1.69 .

In class 1, changes always die out, and in fact exactly the same final state is reached regardless of what initial conditions were used. … The black dots indicate all the cells that change.

Backtracking [in cellular automata] If one wants to find out which of the 2 n possible initial conditions of width n evolve to yield a specific column of colors in a system like an elementary cellular automaton one can usually do somewhat better than just testing all possibilities. … In cases like rules 250 and 254 no initial condition gives the specified column, so all branches eventually die out. … No doubt in many cases the number of nodes that have to be visited eventually increases like 2 t , but many branches usually die off quickly, greatly reducing the typical effort required in practice.

I have tried in the index to give all names in the form they might be used on standardized documents in the modern U.S. … I have dropped all honorifics or titles, except when they significantly alter a name. … Note that this may not reflect where the person was born, educated, did military service, or died.

Ulam sequences Slightly more complicated definitions in terms of numbers yield all sorts of sequences with very complicated forms. An example suggested by Stanislaw Ulam around 1960 (in a peculiar attempt to get a 1D analog of a 2D cellular automaton; see pages 877 and 928 ) starts with {1, 2} , then successively appends the smallest number that is the sum of two previous numbers in just one way, yielding {1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, …} With this initial condition, the sequence is known to go on forever.