The σ-Game and Cellular Automata
Klaus Sutner · American Mathematical Monthly · 1990
1. SummaryIn an article in this journal Don Pelletier discussed the mathematics involved in a little battery operated toy called Merlin (see [3], and also the “Addenda” in this Monthly, Dec. 1987, page 994). Several years ago Stephen Wolfram, in another article that appeared in the Monthly, analyzed a number of simple cellular automata and the fractal patterns generated by some of these automata (see [6]). In this article we point out the close connection between MERLIN-type games and a class of cellular automata related to the ones described by Wolfram. We introduce a game played on directed graphs and give a detailed analysis of the special case where the graph is a rectangular grid. Our analysis uses linear algebra as well as ideas from the theory of cellular automata.