I'm Nathaniel Johnston, a math professor who co-wrote the first-ever introductory textbook about Conway's Game of Life. Ask me anything!
Hi Reddit! I'm Nathaniel Johnston, a mathematics professor at Mount Allison University in Canada. My co-author, Dave Greene (/u/dvgrn0), is also here. Together, we wrote the first introductory textbook on Conway's Game of Life -- a mathematical game in which 2D lifeforms follow very simple rules and yet can do spectacularly complex things.
The book is available for download for free as a PDF at conwaylife.com/book.
Conway's Game of Life was introduced by a mathematician named John Conway in 1970, and people have been finding and building increasingly complex and improbable lifeforms ever since, for more than half a century now. Early discoveries included lifeforms that travel through the plane. Then people started building lifeforms that are capable of doing things like computing prime numbers.
Today's Life pattern engineers can make Life do intricate things like print out the decimal digits of pi, or construct copies of themselves and behave much like real-world "cells" do, right down to having helices of DNA at their core.
So please, ask us anything! We're eager to tell you about Conway's Game of Life.
Edit (10:26am ADT): Sorry everyone, something has come up and I have to step out for a moment. I'll be back to answer more questions shortly (within an hour), and Dave should be joining us soon too.
Edit (11:20am ADT): Back! Answering questions again.
Edit (4:40pm ADT): Thanks for all of your questions, folks! Dave and I will pop in and out over the next couple of days to answer some more questions as time permits, but we won't be as quick from now on (i.e., the AMA is in a "mostly done" state, but we'll come back to it when we can).
Spaceships in particular are notoriously hard to construct, and almost surely can't be found by hand (e.g., by just "trying things" in a Life viewer and hoping that something works), with the exception of the 4 really common ones (glider, lightweight spaceship, middleweight spaceship, and heavyweight spaceship). While those 4 spaceships were all found in 1970, the next one wasn't found until (if memory serves...) 1989, and it was found via a specialized search program.
We're still discovering tiny new spaceships that feel like they should have been found decades ago, since they're just that hard to find. The copperhead is a tiny one that wasn't found until 2016 (also via a search program).
As a teenager in the 90s I had a Conway’s Game of Life program for MS-DOS, and it did provide some hours of fascination (I mean hey, if your computer is too crappy to run Quake 🤷🏼♂️). I enjoyed making big explodey patterns, but a thing I always found interesting is how even the most chaotic storms would ultimately settle down into stable structures (with a few stragglers - usually gliders - here and there leaving the party). Is there anything in the patterns or tendencies of the game that has been successfully applied as an allegory for human (or any biological organism) population behaviours, perhaps over a large time series? I mean, I guess the hint is in the name (Life) but I always wondered if there was any research bearing out direct parallels that could be drawn…
I'm sure Dave will have a better anecdotes and stories related to early Life on underpowered computers than me, since he started playing around with Life decades before me (I started in grade 12, which was sometime around year 2000). But I can try to answer the question regarding Life as an allegory for biological life.
Nick Gotts wrote a really nice paper that explores this question---the idea is that, even though complicated lifeforms are rather rare, once they become sufficiently complicated they start to dominate and appear to be non-rare at much later times.
For example, if you fill the Life plane with random sparse junk, then early-on, you won't see much of anything interesting happen. Mostly just chaotic explosions and junk. But at some point, somewhere in the infinite Life plane, there will be a complex mechanism that is capable of doing things like duplicating itself and/or making other lifeforms to send out to other parts of the plane. And once those mega-lifeforms have had time to do their thing, they will dominate.
Which seems quite analogous to actual evolution: most mutations or sporadic things that could lead to life don't, but given enough time and space, things will line up just right to create lifeforms that are capable of then making life prolific.
I don't have access to the paper, but I have a related question: for those large structures that are capable of replicating themselves and filling the plane, is it possible for them to replicate in a somewhat stochastic way? Evolution requires some sort of "mutation" of the replication mechanism in order for changes to be made. Could a very large system have some small randomness in its replication which allows for this?
If this is possible, it is interesting to imagine that there could be very large structures which are capable of evolution and perhaps increase in complexity over time!
It's a bit tricky to answer to this question, since we often don't know whether or not there can exist a Game of Life pattern with a particular property until someone creates it (or at least provides a convincing outline of how to create it).
At present, the most complicated pattern along these lines that we have is the 0E0P metacell. It can make copies of itself and interact with those copies in lots of different ways, but none of it is random.
If we added some randomness of the form "maybe some cells randomly die and some others randomly come to life", then the 0E0P would fail catastrophically -- it would collapse into a chaotic explosion. I don't know if a pattern can exist that can survive some reasonable amount of true randomness at this single-cell level.
However, if we instead added some randomness of the form "maybe some particular gliders in this section of the 0E0P randomly disappear, while others randomly appear", then the result would be quite like what you described: child metacells that behave differently than their parents start to appear.
Would the vast majority of the gliders not be crucial for its operation? Removing or adding one in the linear propagator usually causes it to either fail to construct the one in front of it or to send off a stream of gliders perpendicularly or something, what proportion of the 0E0P is necessary not for it to work but to prevent escaping gliders that don't affect the instance from which they came? Would the astronomically vast majority of such 'mutations' not cause the emission of debris and a catastrophic chain reaction?
Yeah, there are two different groups of gliders, and I was only thinking about adding randomness to one of them (both groups are housed in the central "nucleus" of the 0E0P, so it's a bit hard to tell them apart without really digging into the details).
Group 1: The gliders that are used to synthesize child metacells. As you said, randomness here would be catastrophic -- it wouldn't really affect the current metacell, but it would cause child metacells to not be formed properly, and likely be completely non-functional.
Group 2 (these are the gliders highlighted as the "lookup table" in Figure 12.18 of the book): The gliders that are used to encode the cellular automaton that the 0E0P metacell is emulating. Randomness here would be OK -- it would just change the behavior of this and child metacells.
Group 1 has a bit over 3 million gliders, and the vast majority of mutations there would cause failure. Group 2 contains up to 28665 gliders, and most mutations there would be fine.
Congrats on publishing!
Will you consider putting a Creative Commons license on your pdf book so that others can use it to teach? A CC BY NC ND will allow someone to use it as a textbook, not edit it, and not profit of if it, while allowing people to download it for free. CC licenses are copyright :). Your employers librarians can help. With the copyright you have (all rights reserved), many instructors wouldn’t be able to use it. There are other licenses, if you wanted others to build off your work (remove the ND, for example).
Sincerely, the Open Education Movement :)
The book actually already has a CC license posted on its git repo, but we admittedly haven't made that clear on the main book website yet. We'll fix that up.
People can use it to teach, and even edit it as long as they provide attribution.
How DO they engineer those humongous Life patterns?
I wish I could give a short answer to this, but I can't! This is exactly the point of the textbook -- to gradually build up to constructing things like the pi calculator.
OK, let me at least sort of try at a short answer: most huge patterns use some combination of gliders and Herschels to send signals from one place to another. Then patterns like Snarks can move those gliders around, and patterns called Herschel conduits can move the Herschels around. By combining all of these things, you can implement computations and constructions (via glider synthesis) of basically anything.
What is an interesting aspect you learned from the Game of Life that seems to have great impact on your view of the world or life in general?
The idea that typical small-scale behavior we can observe is not necessarily the same as large-scale behavior that takes place over eons.
In the Game of Life, if you place just a tiny random smattering of cells (and I mean tiny in the sense of, let's say you turn each cell on with a small probability like 0.001) then the intuition that we get from small patterns is that everything should die off -- each live cell will be isolated, or close to it, so it cannot possibly live on, let alone evolve into some interesting mega-lifeform.
But this is actually very wrong if you apply it to the entire infinite grid: if you turn each cell on randomly and independently with probability 0.001, then you will see absolutely everything happen somewhere. There will be gliders and lightweight spaceships, but also mega-patterns like pi calculators. And there will even be explosive patterns like breeders that cause life to be abundant in the plane, not rare.
How do you feel about the probability that a dead racoon placed in ones locker can lead to net positive results later in life, specifically relating to the publishing of math related textbooks?
Clearly it's a huge net positive, and everyone should strive to have dead raccoons placed in their lockers!
Hi Josh :)
I heard this story many times from a couple of the raccoon relocators... But I'm not sure I ever knew it was your locker
I never actually got to witness it in person (it was cleaned up by the time I got to my locker that morning), so even I can't verify it! I only know what I've been told.
Do you think that the universe is just one large stimulation? After all, physics have increasingly shown that the universe is run by simple building blocks (subatomic particles) to four main rules (the forces.). Or is there more to the universe?
EDIT: Accidently wrote the first word "To" instead of "Do".
I don't personally believe that, but I don't necessarily have a good reason for that belief. It's basically just "I don't see any evidence that we live in a simulation, so I don't believe it".
The fact that we can simulate other universes perhaps shows that ours *could* be simulated, but I don't think it provides evidence that it *is* simulated (any more than the existence of video games provides evidence that we live in a video game ala Free Guy).
whats the best math joke you know?
The problem with math jokes is that there are only a handful of them, so I find myself hearing the same ones over and over and getting sick of them. So maybe instead of posting my favourite, I'll post the most recent one I heard and appreciated (and haven't gotten sick of yet):
What's the opposite of ln(x)?
Duraflame, the unnatural log.
(Credit goes to Bo Burnham)
Did Conway's recent death affect you?
It of course was very sad, but I didn't know him personally so it would be disingenuous to say it was more than that. He was an absolutely amazing mathematician.
Apparently I have to actually ask a question. First off THANK YOU for making the book free in pdf format. My question: what's your favorite pattern/lifeform in the game of life?
I was hoping for this question, so I have an admittedly pre-baked answer to it :)
My favourite pattern has to be the 0E0P metacell (i.e., the focus of the entirety of Chapter 12).
It builds copies of itself nearby, then it communicates with those newly-constructed neighbors so as to compute some junk that determines which of them self-destruct and which of them live on to build additional copies of themselves. It's so intricate and has so much going on in it, that it's somewhat difficult to appreciate just how insane of a construction it is.
The pi calculator (covered in Chapter 9) is probably my runner-up. The decimal printer that is attached to it is such a brilliant addition -- lots of patterns had been made before that compute mathematical things (e.g., prime numbers encoded in spaceship locations). But seeing the decimal digits of pi actually printed on the Life plane (rather than just being encoded in, say, the position of a sliding block) is something else.
Man, this brings back memories of programming in college; my version of Conway's Game of Life programming assignment had to be done in Modula-2 (a Pascal variant).
Do you feel that the programming software and hardware capabilities available now make it easier to explore Life in other permutations? And if the answer is yes, would you have implemented the original version differently if you and your partner had discovered it today?
(I hope that comes across the right way. My discipline in college was computing languages, and I'm always fixated on syntactic differences and advantages.)
Do you feel that the programming software and hardware capabilities available now make it easier to explore Life in other permutations?
Absolutely! I'm somewhat lucky that I came onto the scene after Life was already reasonably easily-implementable -- my first experience with it was in 2000 or so, programming it in Java.
Back in the early days of Life, Life viewing software wasn't nearly as readily accessible, nor was it as easy to make. Heck, in the really early days they evolved Life grids by hand, on Go boards, without the help of a computer at all. I can't even imagine trying to do something like that nowadays, and I can't imagine that we would have half of the interesting patterns we have now without software like Golly to help us view and manipulate them.
Howdy, Nathaniel and David! Why are you giving pdf's of your book away? I am so glad that you are of course, the more people interested in mathematics the better.
Pretty much just agreeing with Dave's response here: the point of the book was to try to help make the Game of Life more mainstream/accessible, since up until now finding out how to build things like the pi calculator has been... difficult to say the least.
Trying to make something more accessible and popular seems to go hand-in-hand with making information about it freely accessible.
That all sounds super interesting guys, but, what do you think about teachers telling us in school that we need to learn maths because we "won't always have a calculator in our pockets"?
I don't find that a compelling argument (but then again I've never taught elementary or high school, so full disclaimer about me not being the perfect person to discuss what curriculum should be there). However, it is important to understand the math well enough that (a) you know (at least mostly) what your calculator is doing, and (b) how to spot when your calculator is telling you something wrong.
If you use your phone to calculate a 15% tip, that's fine. But you should understand what that means well enough to recognize that if your phone says you need to tip $30 on a $60 meal, you probably typed something in wrong.
Hey folks, thanks for doing an AMA!
Something I’ve been randomly curious about - I wonder if anyone has done any experimentation of something Game of Life-ish with “foresight” mixed into the formula for whether to reproduce or not. I.E. Looking at my surrounding square of X blocks (within 1 square in the simple case), in Y iterations, will I have more alive cells or more dead cells if I reproduce? If more alive, reproduce.
Then play around with X breadth and Y depth to see what happens.
I have been curious about it as a proxy to better understanding longer term implications of short term decisions, in a way similar to how the Prisoner’s Dilemma can be informative.
Do y’all know if there’s been any experiments of this kind?
That's a neat question, but unfortunately I'm not aware of any work in that direction. Lots of people have looked at cellular automata that have larger physical neighborhoods (e.g., maybe neighbours and also neighbours-of-neighbours affect a cell's evolution), and people have looked at cellular automata where the evolution can be affected by previous timesteps (Google "cellular automata with memory").
However, if future states can affect a cell's evolution then, as you said, you run into tricky situations like the prisoner's dilemma and the problem of actually evolving the CA to see what happens. A cellular automaton where you have to solve a long-running SAT instance just to evolve a pattern seems like a lot of work!
I’ve seen GOL used for cool visualizations and for demonstrations of emergent behavior, but can GOL-like systems be used to efficiently solve any problems? Is it a tool worth learning? The pi calculation, for instance - is it more computationally efficient, a more succinctly expressed algorithm, or easier to understand than other pi calculation methods?
I'm not aware of any situations where a GoL pattern can do something more efficiently than could be done otherwise (and I doubt such a pattern exists).
For example, the pi calculator in Life works by using a spigot algorithm (PDF warning) that could be implemented "directly" by a computer program so as to compute those digits much quicker. On a typical desktop computer you could run the Life pi calculator to the point of getting 15 or so decimal digits in a single day. Computing those digits "directly" would of course be significantly faster.
The reason for this is that the Life pi calculator is really just mimicking a regular computation. Want to add 1 to an integer? Send a glider over that way and make it push that block. In a regular (non-Life) computation you can do that much more directly -- you don't have to compute the path of the glider and all of the things that it does on the way to pushing the block -- you just change a couple of bits in memory, without the extra layer of abstraction in the middle.
Do you think the game of life and cellular automata theory as a whole can be the subject of some meaningful research or will it always be a sort of mathematical toy?
I'd like to see research in it become more mainstream, but if I'm being honest I don't really expect it to. It's difficult to get granting agencies, for example, to want to fund something like the Game of Life if there's no a clear application (besides somewhat vague parallels with biological systems).
There are sometimes some inroads made along the lines of "let's use the Game of Life as a test case for this SAT solving method". This has led to research papers on the still life density problem (PDF warning), for example, and more recently the unique father problem (which I believe has a research paper currently being written). But that connection with another more mainstream topic (like SAT solving) seems to be a necessity.
Has anyone made a physical/mechanical version?
I've seen a Lego version which was a little limited, but impressive nevertheless.
Oooh I'd love to see that, but I've never seen a fully mechanical implementation (so if anyone else has, please let me know!)
I met John at Oregon State Univ quite a while ago during my grad work where he was presenting his proof of the non-existance of free will. He was really engaging, but a terrible presenter. Did you get the chance to meet/work with him at all? If so, what were you experiences?
The closest I ever got to meeting John was from across a room at a math conference that we both attended -- I never actually got the chance to speak with him.
He didn't give a formal math talk, but he did present a couple of open problems that he was curious about (one was his "climb to a prime' conjecture, which was open at the time). I don't remember much of my impressions other than (a) he was extraordinarily social, and constantly surrounded by people, and (b) the problems that he presented were really interesting.
What do you think about the word "game" in the name of Conway's invention/discovery/rules?
I know the rules were first published in a column called "Mathematical Games" and the editor said: "Because of Life's analogies with the rise, fall and alterations of a society of living organisms, it belongs to a growing class of what are called 'simulation games' (games that resemble real-life processes)."
But it seems to be really stretching the definition of what a "game" is.
I agree that it's hard to consider it a "game" when there is no interaction. Rather, in my mind, the "game" is the part where you come up with patterns that do neat things, not the part where you "play" it (i.e., evolve the grid).
In this sense, it's a "game" kind of like Minesweeper or Solitaire are games, but more free-form (or would it be more like a "toy" like Lego?... I'm not sure).
Really, I don't think it's too far off to think of math as a whole kind of like a game: we have a set of rules (axioms and logic) and our goal is to find novel ways of manipulating and exploring those rules so as to reach a win condition (a new theorem, for example).
I've noticed a bit of a trend lately where people will attempt (and sometimes suceed) in creating Conway's Game of Life in systems which are found to be Turing Complete. Do you think this status of being "Conway Complete" is a useful or interesting distinction, or is it perhaps just the result of a system with the right level of graphical capabilities being Turing Complete?
I think it's just a result of "is Turing complete + has graphical capabilities", like you mentioned at the end of your comment. At least if the system is flexible enough that it can turn on/off pixels of the display independently (i.e., it doesn't have any silly restrictions like "if you turn on pixel 1, you cannot turn on pixel 2").
If a system can emulate Conway's Game of Life then it necessarily is Turing complete (since the Game of Life is) and has display capabilities. Conversely, if the system is Turing complete and is capable of using the results of computations to manipulate its display pixels independently, then it can emulate Conway's Game of Life and print them to a display.
I just learned about gol a while ago and find it fascinating, what is your favorite pattern that you have seen?
Rather than duplicate my comment, I'll point to my answer here. :)
Is there a mathematically rigorous definition for when a pattern has "stabilized"?
Not to my knowledge -- it's the type of thing that seemingly becomes problematic no matter which definition you try to use (see this thread on the ConwayLife forums for example), so it's treated mostly as a "I know it when I see it" thing in the community.
You can try things like "is made up of non-interacting still lifes, oscillators, and spaceships", but then things like the Gosper glider gun have not stabilized. A similar problem occurs with the potential definition "its population is periodic" (that definition also has other problems too).
You could try patching this up by saying things like streams of gliders are OK, or linear population growth is OK, but it's a never-ending game of patchwork, just tossing in a never-ending stream of patterns that we consider to be stabilized. We have patterns that are completely predictable and have population growth rates like O(n1.5) -- surely they should be considered stabilized too.
You also run into computability issues. When does the Fermat prime calculator stabilize? Well, we don't even know if it keeps growing forever, or if it self-destructs at some point! We understand what that pattern is doing, but I can't imagine that it's OK to say that it has "stabilized" at generation, say, 1000000 if we don't even know if it self-destructs at some (much) later timestamp.
When you created the Game of Life, were you aware that a game with such simple rules could/would turn into such a complex thing that people ended up creating?
To be clear, neither Dave nor I made the Game of Life -- that was John Horton Conway, who sadly passed away about 2 years ago.
IS there an ELI 5, am not even understanding the questions. What is this book about?
Ah, sorry about that. There's a Wikipedia page about Conway's Game of Life, but it's easiest to understand by actually "playing" it (e.g., go here and draw some stuff on the grid and press the "play" button).
It's a game played on a 2D grid in which each square of the grid can be either "alive" (black, in the link above) or "dead" (white, in the link above). From one timestep to the next, alive cells stay alive if they are touching 2 or 3 other live cells, but otherwise they die. Dead cells come alive if they are touching exactly 3 live cells, but otherwise they stay dead.
And that's it! The neat thing about it, though, is the fact that there are such interesting and weird things that can happen in the grid when these birth/death rules are applied.
It's 5:30 am on the west coast, don't you think that's a little early for an ama?
Ah, apologies -- I'm on the east coast and wasn't thinking. I'll be around all day answering questions though!
I've tried creating Flyer lifeforms in the past but they all seem to fizzle out quickly. Is there something that traveling lifeforms all have in common to use as a predictor that they will not only survive more than a few cycles, but move across the plane?
View HistoryShare Link