On December 28th 2020 The New York Times posted an article consoling us on the passing away of the great mathematician John Horton Conway and celebrating one of his life’s biggest achievements – Conway’s Game of Life. You can see the article here One of our colleagues Adam P. Goucher was mentioned in the article for his contribution and discoveries in the Game of Life, this is what he had to say about the game:
I got introduced to Conway’s Game of Life when I was 13 by my father. I already had an interest in Math and Computer Science, though I guess it is intertwined with my interest for the game as well.
What attracted me to the game was it’s property of universality, it’s provable that you can essentially build any computer that can compute absolutely anything and that it is possible to create a self-replicating machine. Even though it was proven at that time that a self-replicating machine was possible it had not been done (at that time). It was also the flexibility -- from these simple rules you create arbitrarily complicated emergent phenomenon.
“There are 2 different types of patterns, those that are discovered and those that are invented.”
There is a spectrum of completely naturally occurring, more simple patterns that you can find by starting from a random initial configuration. They are discovered because they appear from randomness and appear naturally. Then on the opposite spectrum, there is something like Paul Rendell’s Turing Machine.
That’s a huge pattern made of things that visibly look like electric components transmitting information between each other. Made by a human, who took a design for a computer and translated each logic case individually into a component.
The most ambitious pattern that I have designed is a self-replicating unit cell called – 0e0p Meta Cell. It is the most ambitious because of the number of components and prerequisites needed to create it – it has more than 18 million cells. It is a universal constructor that can build virtually anything you want, as long as you give it the construction recipe in what you could call its DNA. You can learn more about it from the video below: (turn CC on for the non-French speakers)
What is IKPX?
To understand what IKPX is we first need to know what a Sap Solver is. You give it (sap solver) a bunch of logical constraints, you define variables and give them constraints in the form either X or Y must be true or if Y is true Z is true. And it tries to solve them to see if there is a solution to this. Essentially Boolean equations that are either true or false and tries to find solutions that fit these simultaneous equations.
What IKPX does is it uses Sap Solvers to create spaceships, which are patterns in Conway’s Game of Life that travel, they evolve into translated copies of themselves. So if you keep running the rules they drift in some direction.
IKPX maintains a pool of possible front ends to add these spaceships and tries to extend them backwards. It extends them a roll at a time until it finds a complete spaceship. It uses the Sap Solvers to look ahead to see possible ways to extend this partial spaceship. Eventually (as well as hopefully), finds a tail that produces a complete spaceship. The most interesting discovery from this is “Sir Robin” (which is the pattern mentioned in The New York Times) jointly discovered by Tom Rokicki.
Tom had found the first 2/3 of it, but didn’t know in advance how close he was and eventually gave up having spent weeks of computing time. And asked if someone wants to have a go at this. So I added Tom’s front end into my IKPX search program and over the course of 8 hours managed to complete it. There was such media attention to this, in particular, is because it ended in the front page of HackerNews (a website similar to Reddit but for Computer Science). It’s so interesting because it travels in the direction of a knight in chess. Prior to this, every elementary spaceship travelled orthogonally like a rook or diagonally like a bishop. This is the first and effectively only naturally discovered spaceship that travels in an oblique slanted direction
Conway’s Game of Life has a very large community that has evolved over time, the Game of Life was first published in October 1970 and started out as disjointed groups of students in universities, interestingly, Conway’s group which was in the Cambridge Math Department. A group of hackers led by Bill Gosper from MIT started working on it as well. They discovered the Gosper Glider Gun, the first pattern that grows infinitely by producing this stream of gliders.
On the way into the 80s, people worked on a proof that a self-replicating machine is possible. Although there wasn’t one until the self-replicating meta cell. It was proved possible in the 80s but the proof was… not practical. The pattern itself would be gigantic -- much larger than the self-replicating unit cell.
In the early 1990s, there was an email that was set up for these disjointed groups to communicate - there were 50 or so people. The email list was largely active until the late 2000s when it became a public set of forums, where most of the discussion takes place now.
It is great to see that the community has expanded and is expanding more rapidly than ever, it was very niche when it was a mailing list, now it is a forum that anyone can join and there are a few hundred active users.
