Recently I mentioned that mathematician John Conway died last April. To his eternal disgruntlement, he is most famous for his “game” of Life — something he considered trivial and inferior to his real mathematical work. That fame is largely due to a Martin Gardener column in Scientific American — the most popular column the magazine had published up to then.
I said I wasn’t going to write about Life because it’s such a well-covered topic, but I thought I might whip up an implementation in Conway’s honor. (Went there; did that; videos below.) Getting into it made me realize Life connects back to my virtual reality posts.
So it turns out I am going to write about it (a little).
First, credit due, watching an old interview with John Conway (two, actually) on the Numberphile channel triggered this post. It was some of Conway’s comments that connected dots between his Life game and my posts.
What struck me in the context of my earlier posts is that Life isn’t just a virtual reality being run on a computer. It is a virtual reality that is itself a computer doing a computation.
Simply put: Life is a computer.
Conway’s “game” of Life is simple to describe:
- It’s played on a 2D grid of “cells”.
- A cell can “alive” or “dead” (on or off).
- The game proceeds in cycles (or clock ticks).
- Each cycle each cell does a calculation.
- If it’s alive, it requires 2 or 3 living neighbors to stay alive.
- If it’s dead, it’s reborn if it has exactly 3 living neighbors.
- A game starts with a (typically random) cell pattern.
That’s it. That’s all there is to it. You can play it with graph paper.
You could play it with a chessboard, but alternating color of the squares might be distracting. It would work fine if you just treat it as an 8×8 grid, though.
The problem with a chessboard is that it’s only 8×8, which is small for Life other than playing with simple shapes. A Go board would work a lot better, and you could use white stones for live cells and black stones for dead cells.
Or course, where it works best is with a computer:
That’s my first draft at a Conway Commemoration, and it illustrates one of the key points of this post: The computation was still going at the end of the run.
The nature of my code (for now) is that I tell it how many cycles of Life to generate, and it goes and creates a bunch of image frames. I use ffmpeg to stitch those together into a video.
The point is, I can only guess what the state of the “board” (system) will be after X-many cycles. It might have entered a loop, or it might still be going. There’s an outside chance of clearing the board, but I’ve never seen it.
One point Conway made is that there is no way to predict a given state other than to run the system that many cycles. This is effectively the Turing Halting problem — there’s no way to predict a latter state of a computation other than to run the computation.
The bottom line for me is that some of the videos end with a continuing computation, whereas others end in a loop:
Which is my second draft at a Conway Commemoration.
One key difference is this one wraps the right-left and top-bottom borders (the first one had edges). Obviously the color scheme is different, too.
Another thing about Life is that its computation isn’t reversible.
The way Life works loses information. If you watch it in reverse, cells appear out of nowhere (i.e. with no rules explaining their appearance). The cell movements defy the rules — defy the “physics” of the virtual reality.
It can be mirrored or flipped — it’s symmetrical in space, but it’s not symmetrical in time.
There are those who wonder if information really is conserved. It seems it can be created, which suggests it can be destroyed. (If so, it would resolve the black hole information paradox.) Certainly in the game of Life, information is destroyed.
As I mentioned, it’s possible for the board to clear, for all cells to die in a given cycle. When that happens, the information loss is total. (And there can be no new life, since a cell requires three living neighbors for birth.)
As a trivial example, imagine the first cycle consists of all cells alive. Since each cell then has eight living neighbors, on the next cycle, all cells are dead. This applies to most starting distributions with a high frequency. Too many cells in the first round results in a vast die-off.
The physics of our world is reversible at the fine scale, but entropy destroys it in larger systems.
Unbreaking an egg might be possible on on theoretical reductionist level, but the requirements are beyond formidable. Flying pieces lose energy due to friction and gravity; reversing that takes constantly applied energy to accelerate them. (And I’m dubious it’s possible to fuse eggshell using only fairly low-speed impact.)
So while our reality might be reversible in principle, I’m not sure it applies much beyond the quantum or micro realm. Certainly at our macro level, reality isn’t reversible and information clearly is lost.
Just like in Conway’s version.
That’s the first official version. It implements color fading as cells “age” — survive through cycles. New cells are white, then yellow, green, and finally a dark cyan. (I need to stretch the delay so the individual colors stand out more.)
I used 2×2 pixel cells here, and, while it’s interesting in its own way, I think I like the chunkier cells (4×4 seems about right). The video below uses 1×1 cells!
I also restructured the code into something I’m not embarrassed by, hence the version 1.0. (There’s an old protocol: 1. Make it work. 2. Make it work right. 3. Make it work fast. The first two versions were getting it working. This version takes it to step two.)
A Life game grid has X many columns and Y many rows. That means it has X times Y many cells. (X and Y are arbitrary; they can be whatever we want.)
Since a cell has two states — alive or dead (on or off, if you prefer more gentle terms) — that means the total number of states a Life “computer” can have is:
As I write this I’ve got my app generating a version for 1920×1080 HD. I’m using 4×4 cells, so the grid is 480×270, which means it has 129,600 cells.
2(480×270) = 2129,600 ≈ 1040,000
Which is a lot of states, although it’s not a given that all states are possible.
The point is that we can view each cycle of Life as a (very large) binary number. Each cell is one bit, and we can just read them off left-to-right and top-to-bottom. (Which happens to be the way the cells are set up in computer memory.)
Therefore a game of Life is a series of large numbers representing a calculation. It just so happens we can watch this calculation in action as it unfolds.
This one uses 1×1 cells, which does make it look more organic, even if I prefer the larger cell size. It consists of 6000 frames and took all night to render.
What Conway and his cohorts demonstrated is that by setting up explicit starting configurations of cells, it’s possible to treat Life as a Turing Machine.
It’s capable of doing any calculation a TM can do — which essentially means it can do any calculation. (That is not to say easily, cheaply, or quickly.) I’ve seen videos of a Life Full Adder in action. I’ve even seen Life implementing an actual Turing Machine, tape and all.
More to the point in terms of my previous posts, Life is a great example of implementing a virtual computational system. How a game of Life proceeds has nothing to do with the underlying mechanism. As I said, you can do it with graph paper or a Go board.
Life is an information system, an abstraction, so it’s easily implemented in myriad ways with the same result. It’s distinct from the implementation, so how it’s implemented is irrelevant.
It’s an even better demonstration than the Eight Queens example!
This version uses the 4×4 cell size, which I like a lot better. Also a slightly slower framerate, 4 fps rather than 5 fps.
As you see, this run ends in a tight loop repeating the same giant numbers over and over.
It seems right to have done this Conway Commemoration thing in Python.
I’ve done a version of Life in just about every other language I’ve used, but by the time Python came around I’d all but retired and Life implementations were more a pursuit of my younger days. (Plus: implementing Life in a scripting language isn’t something I’d really even think to do.)
That said, Python has become one of my favorite of all languages, so it’s high time I got around to Life, and what better occasion than in memory of the guy who invented (to his everlasting regret) the game.
Stay Life-ly, my friends!