12
$\begingroup$

I have been looking for books on cellular automata, and I really can't afford more than one book right now, so I really need to make the right choice. What would be the right book for someone with a Computer Science Masters degree and also feels comfortable with Mathematical Logic and basic Abstract Algebra? (Or, to make the question more useful to others, what are the target readers of the most recent books on cellular automata?)

$\endgroup$
1
  • 2
    $\begingroup$ The OP sounds like someone looking to start in this subject. For that I would have to recommend Sipser's Introduction to the Theory of Computation because it covers this topic nicely (for a first course on it) and because it covers so much else. If one likes cellular automata then Sipser's book allows you to study many other similar things. Link: amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/… $\endgroup$ Jun 28, 2011 at 0:16

9 Answers 9

14
$\begingroup$

First, there is an unannotated list of books on cellular automata here. Second, if you are going to get just one book, then I think it has to be Wolfram's A New Kind of Science, which, despite its flaws, is the source of so much of the research in cellular automata that it must be confronted first. [I see I am concuring with Kevin O'Bryant's just-posted recommendation.] You might read the review by Lawrence Gray in the Notices of the American Mathematical Society (February 2003) to make yourself aware of the controversies surrounding this book. If you can overlook its flaws, it is a remarkable book, and quite fun to work through.

$\endgroup$
2
  • $\begingroup$ +1 for the nice list of books. $\endgroup$
    – lhf
    Jun 23, 2010 at 12:30
  • $\begingroup$ I also agree, ANKOS is a good reference, if you're looking for a book. $\endgroup$ Mar 4, 2021 at 13:02
6
$\begingroup$

There's a Cellular Automata and Groups by Ceccherini-Silberstein in Springer Monographs in Mathematics. It's self-contained and introduce the CA with group theory.

$\endgroup$
1
  • 2
    $\begingroup$ Personally I found this book very useful, it could be the perfect choice if you prefer an algebraic perspective $\endgroup$ Oct 3, 2012 at 13:06
4
$\begingroup$

I know the flames are coming, but I can't stop myself. You might enjoy "A new kind of science", by Stephen Wolfram. It's available free online, and has quite a bit of code and quite a few fun experiments inside.

$\endgroup$
5
  • 7
    $\begingroup$ I really want to flame you, but I'm not sure about what I can get away with =D! $\endgroup$ Jun 23, 2010 at 12:10
  • 3
    $\begingroup$ How many pictures of the Sierpinski gasket can you stand? A much better and more interesting book about the connection with physics is Chopard and Droz: books.google.com/books?id=x5t9c_F_rZAC $\endgroup$ Jun 23, 2010 at 12:37
  • $\begingroup$ See also "Cellular automata and lattice Boltzmann techniques: An approach to model and simulate complex systems" by Chopard et al., which will be downloadable if you look on Google Scholar. $\endgroup$ Jun 23, 2010 at 12:43
  • 1
    $\begingroup$ In all seriousness, I really don't like the amount of "woo" (controversial scientific claims without sufficient support) in this book. $\endgroup$ Jun 23, 2010 at 22:14
  • $\begingroup$ @Harry: agreed. But even so, it has much to recommend it. $\endgroup$ Jun 24, 2010 at 3:11
4
$\begingroup$

There's also "Cellular Automata Machines: A New Environment for Modeling" by Toffoli and Margolus.

$\endgroup$
5
  • $\begingroup$ I see -- I suppose then that it's not dated? $\endgroup$
    – Jay
    Jun 23, 2010 at 13:43
  • $\begingroup$ It is. See my comments to Kevin O'Bryant's answer. Lattice Boltzmann (esp. LBGK) models (en.wikipedia.org/wiki/Lattice_Boltzmann_methods) are the very best way to simulate complex fluids, not least because they're well suited to GPUs (see NVIDIA's CUDA app page). The word "Boltzmann" does not even occur in here. This book is barely new enough to cover FHP lattice gases, to say nothing of 13-velocity models. $\endgroup$ Jun 23, 2010 at 13:58
  • $\begingroup$ @Steve "the very best way to simulate complex fluids" stands in need of justification. Good ol' fashioned advection/pressure projection is also very well suited to CUDA. If LBGK is provably better (according to some reasonable metric for some reasonable problem domain) I'd really really love to see details. $\endgroup$
    – Dan Piponi
    Jun 23, 2010 at 21:38
  • $\begingroup$ By complex I mean stuff like emulsions, porous geometries, etc. The boundary conditions for non-lattice techniques are much worse than they are for the lattice techniques (which have the same set of problems irrespective of the detailed geometry). There is a reason why the geologists are using this stuff. $\endgroup$ Jun 23, 2010 at 22:17
  • $\begingroup$ @Steve Thanks. Sadly my work is full of 'simple' rather than 'complex' fluids :-) $\endgroup$
    – Dan Piponi
    Jun 23, 2010 at 22:33
3
$\begingroup$

While Wolfram's A New Kind of Science (2002) is a beautifully-produced book and is lovely to look at, I find Wolfram's papers collected in Cellular Automata and Complexity (1994) much more informative. Because the papers were written for research publications they provide many of the technical details omitted from A New Kind of Science, which appears to have been written with a more general audience in mind.

You might also want to read Melanie Mitchell's review of A New Kind of Science. It appeared in the journal Science 298: 65-68. The review and Mitchell's insightful "Computation in Cellular Automata: A Selected Review" are available on her web page under "Publications."

$\endgroup$
2
$\begingroup$

I can't improve on the list in Joseph O'Rourke's answer, but I'd like to mention that Winning Ways gets on the list because of its discussion of Conway's "Life" cellular automaton. In particular Winning Ways outlines a proof that "Life" harbors a universal Turing machine. For more news on "Life" try this article, describing the recent discovery of a self-replicating pattern. The pattern is a little disappointing because it is destroyed in the process of making a copy of itself, but this leaves some interesting open problems:

"Another milestone might be a self-replicating pattern that creates increasing copies of itself, or a space-filling replicator that can make multiple copies to eventually fill an arbitrarily large area of the Life plane,"

$\endgroup$
1
  • 1
    $\begingroup$ The pattern deliberately destroys itself, separately from the process of making a copy; its destruction is not just a side effect, but an intended part of the pattern. For even more news about Life and related automata, there's another book Game of Life Cellular Automata (edited by Andrew Adamatzky) coming out this summer. Disclaimer: I have one of the chapters in it, also online at arxiv.org/abs/0911.2890 $\endgroup$ Jun 24, 2010 at 4:10
1
$\begingroup$

This is a research list on evolving cellular automata - mostly stuff about finding CA rules with genetic algorithms but also CA only references.

Hope it helps.

$\endgroup$
0
$\begingroup$

Adamatzky's Game of Life Cellular Automata gives a fairly broad overview.

$\endgroup$
0
$\begingroup$

Aladjev V.Z. Classical Cellular Automata: Mathematical Theory and Applications.[Dash] Germany: Saarbrucken, Scholar`s Press, 2014, ISBN 9783639713459, 517 p.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.