Notes

Chapter 11: The Notion of Computation

Section 2: Computations in Cellular Automata


Other examples [of cellular automaton computation]

Rule 152 and rule 144, which effectively compute Ceiling[n/2] and Ceiling[n/4], respectively, are shown below with n = 18 initial black cells.

Other examples [of cellular automaton computation] image 1

As discussed on page 989 rule 184 effectively determines whether its initial conditions correspond to a balanced sequence of open and close parentheses. (Rule 132 can be viewed as being like a syntax checker for a regular language; rule 184 for a context-free language.)

From Stephen Wolfram: A New Kind of Science [citation]