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]

Ceiling[n/2] and Ceiling[n/4]
Ceiling[n/4]
, respectively, are shown below with n = 18
n = 18
initial black cells.

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]