Ask HN: Looking for a Book on Cellular Automata

My information is pretty dated but I found Wolfram's collected papers a very good read (Amazon lists it as ~$40 but you can get it for under $5 used) [1]. I wouldn't be surprised if you could find a torrentable version as well.

You have to be careful about what kind of cellular automata you're talking about. There's the 'toy models' such as 1d and 2d cellular automata that Wolfram and Conway's Game of Life [2] fall into but there's also many others, including lattice gases and more complex modeling options. I assume you mean the cellular automata that have the flavor that Wolfram and Conway are talking about.

The linked Wolfram book is a 'classical' treatment where he introduces different classes (I,II,III and IV) of cellular automata, ranging from completely ordered (1d, rule 0, say) to completely disordered (1d, rule 32, say).

I hope I'm not rambling too much but from what I understand it was a commonly accepted that 'complexity happens at the edge of chaos' [2]. Wolfram's "A New Kind of Science" (again, from my understanding) essentially represents an evolving view (by Wolfram) where he graduates from "complexity happens at the edge of chaos" to "complexity is the norm, rather than the exception". Wolfram coins this as the "principle of computational equivalence" [3]. People have recommended ANKoS and I would really recommend against reading it. I think the principle of computational equivalence and the proof that rule 110 is Turing complete (given in ANKoS) are interesting but they're so buried in exceptionally bad writing as to be not worth the effort.

If you're interested in studying Conway's Game of Life [4] more, there's Golly [5], which is a wonderful piece of software. Cellular automata is a very large field and there are lots of different questions to ask about it, so you might want to limit your scope if you want more directed suggestions.

As a sort of tangential recommendation, I would highly encourage you to check out "Complexity and Criticality" by Christensen and Moloney [6]. Though they don't talk about the cellular automata that are described above, they motivate a lot of the different concepts of criticality, phase transitions and other motifs that show up repeatedly when discussing these models and others like them.

[1] https://www.amazon.com/Cellular-Automata-Complexity-Collecte...

[2] https://en.wikipedia.org/wiki/Edge_of_chaos

[3] http://mathworld.wolfram.com/PrincipleofComputationalEquival...

[4] https://en.wikipedia.org/wiki/Conway's_Game_of_Life

[5] http://golly.sourceforge.net/

[6] https://www.amazon.com/Complexity-Criticality-Advanced-Physi...

I second the recommendation with the caveat that you can only get through it if you can stand his narcissism.

It's really a tragedy because there really are brilliant ideas in there. It's just that Wolfram did not single handedly invent them all.

I would also recommend the Artificial Life conference proceedings and journals.

I don't think he quite claims that he single handedly invented them all, but yes, Wolfram's style is pointedly awful. I'm surprised I was open-minded enough to get to the good parts of the book... The surprising existence of the cone-shell pattern alone made it worth it.

I personally feel that Wolfram is excellent at explaining things, it's his self-aggrandizing after some number of pages that gets irritating. Luckily, he often gets to the gist before that.

A basic introduction, as well as suggested readings, can be found in the book Biological Computation, which I co-authored http://t.co/JzWrcnSzB3

I am especially fond/proud of the detailed explanations of the proofs of computational universality of CA.