Ask HN: Looking for a Book on Cellular Automata | Hacker News Reader

Ask HN: Looking for a Book on Cellular Automata

63 points_hrkg32 comments

I'm self-studying cellular automata and I'd love if there were any sitebooks or torrentable textbooks.

Surprised no one has said "A New Kind of Science" by Stephen Wolfram. While not quite a new kind of science, it is all about cellular automata.

http://www.wolframscience.com/nksonline/toc.html

ANKOS was in fact mentioned already, a couple of hours ago:

https://news.ycombinator.com/item?id=11982034

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.

Although Shalizi has his own biases and is pretty opinionated, his review of "A New Kind of Science" is quite interesting and is worth considering: http://bactra.org/reviews/wolfram/

Chapters 11 & 12 of the free textbook "Introduction to the Modeling and Analysis of Complex Systems" [1] are on cellular automata. The "Complex Systems" journal has many papers on CA. [2] (I've just finished a project where we implemented a random number generator using a cellular automaton, might be nice to see. [3])

[1]: http://textbooks.opensuny.org/introduction-to-the-modeling-a...

[2]: http://www.complex-systems.com/archives.html

[3]: https://sunsistemo.github.io/mozzacella-automato-salad

While not just about this, The Computational Beauty of Nature [1] is worth checking out.

[1] https://www.amazon.com/Computational-Beauty-Nature-Explorati...

This is my all-time favourite book! Reading it way back in the day is what convinced me that studying Applied Mathematics & Computer Science was my path in life. Absolutely incomparable, I loved it mainly because it's a grand tour of everything that is amazing and the author doesn't shy away from code, formulae, and background (OGY Control, eigenvalues & eigenvectors!) necessary to really grasp the concepts and implement them.

I believe it's out of print now, but if you can find it, check out "The Recursive Universe" by William Poundstone. It centers around Conway's Game of Life, but every other chapter branches out to draw connections with other topics, like biology, information theory, and thermodynamics.

Dover started republishing it a few years ago and it's even available on Kindle.

Definitely a fun read and worth the $10 and the couple evenings it takes to read.

This book made a deep impact on my worldview.

Not sure about books entirely about cellular automata, but Stephen Wolfram's "a new kind of science" has a LOT on cellular automata.

Also check out his papers if you're interested in them

+1 for ANKOS

Think critically when reading this book, it contains a lot of fluff and self aggrandizing. It was self published, and the author(s) claimed it would be a "paradigm shift" in science, with very little impact after a decade+. [0]

[0] https://en.wikipedia.org/wiki/A_New_Kind_of_Science#Receptio...

I'd strongly suggest not reading ANKOS until you already know what Cellular Automata are and how they work.

First because Wolfram is not actually very good at explaining things: he's a very smart guy, but very smart guys don't necessarily know how to lay new concepts out so that other people can grasp them. Second, a MAJOR problem with the book is that he does not admit any sources outside himself: the inventor of CA, John von Neumann, is _never mentioned in the main text_.

You come away understanding only what Wolfram thinks is important, which has a lot more to do with him than with the subject. It's a book worth reading, but it's not an introduction.

(I won't even get into his tortured writing style, for which he actually had to include a little apologia in the introduction.)

I feel the need to voice some moderation in response to this response.

ANKOS is sometimes painful to read for Wolfram's incessant self-aggrandising, and it is also frustratingly unstructured in parts. Nonetheless, many of the digressions are thought provoking in ways that you won't really find in any other book. Further, it is mostly non-technical and informal, so it can serve well as a very broad introduction to some of the curious corners of cellular automata research.

>it can serve well as a very broad introduction to some of the curious corners of cellular automata research.

This is true. It's a substantial book, well worth reading despite its flaws. The thrust of my post was that it should not be the _first_ thing you read in order to begin learning about CA.

Forget reading, the first thing you should do is write your own version of "the game of life", which I did as part of my CS class in 8th grade. Just be careful, youtube might suggest you do it in APL, don't do it in APL.

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.

This is a kinda good theoretical intro: http://plato.stanford.edu/entries/cellular-automata/ and search the Santa Fe Institute's site too: http://www.santafe.edu/search/results/?query=cellular+automa...

This is a good introduction: http://natureofcode.com/book/chapter-7-cellular-automata/

Love this book!

It is especially good for beginners.

My favorite one is, by far, "Cellular Automata: A Discrete Universe" by Andrew Ilachinski (2001). It goes deep into the juicy details and has only a limited amount of hand waving. You can probably find it in the local math/physics department library, or in the usual internet sources ;)

There are also some articles from Wolfram that make good introductions. Mostly those from the old days in which "I" wouldn't be the subject of every second of his sentences. In particular:

Universality and Complexity in Cellular Automata Physica D: Nonlinear Phenomena 10, no. 1–2 (1984): 1–35

Computation Theory of Cellular Automata Communications in Mathematical Physics 96, no. 1 (1984): 15–57

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.

Here's what we had to say about books mentioned in this thread:

Schiff, J.L. 2008. Cellular Automata: A Discrete View of the World.John Wiley & Sons. A readable introduction to cellular automata and their applications.

Wolfram, S. 2002. A New Kind of Science. Wolfram Media. A very ambitious book trying to demonstrate in detail (the book contains 1,197 pages) that the entire universe around us (e.g., biological, physical, and computational phenomena) could be and should be considered as cellular automata. While the approach of the author is a matter of heated discussion, the book is thoughtprovoking and contains many interesting examples.

Ilachinski, A. 2001. Cellular Automata: A Discrete Universe. World Scientific Publishing. A detailed (approximately 800-page) and technical exposition of cellular automata. Includes detailed discussions of various theoretical techniques for studying cellular automata behavior. The proof of the universality of Life is presented in detail. Among the topics covered are probabilistic CA, the relationship between CA and physics models, and a comparison between CA and neural networks.

https://mitpress.mit.edu/books/cellular-automata-machines

The greater part as I remember it is on ideas and applications; a substantial fraction covers their particular system.

I second this book. If I recall correctly, it shows implementation on their fairly unique hardware, but getting their examples working in a modern CA library shouldn't be impossible.

I'd recommend "The Lifebox, the Seashell and the Soul" (readable online at [0]). It's wacky at times, and not deeply rigorous, but thoroughly enjoyable. But not a textbook.

[0] - http://www.rudyrucker.com/lifebox/

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...

Wolfram has put the entire text of Cellular Automata and Complexity: Collected Papers online

http://www.stephenwolfram.com/publications/cellular-automata...

The survey papers in this collection would be the place for OP to start; note that some of the other papers assume a significant background in mathematics and physics.

have you tried googling for "books on cellular automata"? also consulting Wikipedia, Amazon, YouTube, etc, more directly?

I am amused that this very reasonable and constructive, and "teach a man to fish" kind of comment of mine has been downvoted to -1.

HN ownership/mods: please remove the ability to Downvote. it's clearly being abused. do you want to have a community of smart, helpful people with free discussion, with the goal of mutual improvement? or do you want a community of assholes and heavy HiveMind/ThoughtPolice effect?

a follow-up related challenge is do you want HN to become the sort of website where anyone can ask, for example, "what is foo?" despite <foo> being a thing that that very same someone could have gotten reasonable answers/education about by just googling about? What is sex? What is algebra? How do I learn about computers? What is a website? What is a web browser? What is HN? Who is PG? What is the English language?

Are these acceptable questions for the caliber of people you'd like to attract and retain here on HN? Do you realize that some people are just gaming your system? Do you realize that some are carrying out stealth self-promotion, while playing innocent? Where do babies come from? Which key do I press to submit this comment? How do I use the Chrome browser? Are these all acceptable post topics and comments here on HN as well? (This should be a fair question given the recent mod and community track record to date.) What is "Star Wars"? Who made "Linux"? What is a "pineapple"?

Reply on news.ycombinator.com