Conways Game of Life!

Wednesday, January 15th, 9:43PM

One of my favorite examples of cellular automata is Conway's game of life. 4 simple rules on a grid create complex systems (oscillators, glider guns, even a general purpose computer). It's a zero player game–meaning that the game play is determined solely by its initial state.

The four rules are as follows:

1. A live cell dies if it has fewer than two live neighbors.

2. A live cell with two or three live neighbors lives on to the next generation.

3. A live cell with more than three live neighbors dies.

4. A dead cell will be brought back to live if it has exactly three live neighbors.

Here is a quick simulation I made in javascript:You can manually click some of the boxes to create the starting conditions, or you can just click randomize.

Conway's game of life is turing complete–meaning if you have a large enough grid, you could perform any operation on it that you could perform on any other computer. This is really well demonstrated by Phillip Bradbury on github,who created a game of life that so large that it starts simulating conway's game of life again

. Theoretically, this could keep going–you could create a Life game that simulates a Life game that simulates a Life game that simulates a Life game….

The simulation I made is only 30 x 30 px, so you won't be able to make anything too complex. But if you're interested, I would recommend checking out golly, which has a built in script to generate metapixel grids that let you do some wacky things with Conway's game of life.

(If you ever want the code for how I make these simulations just email me!!!!!!!)

If you've ever read the time traveler's wife, you might remember the quote “Everything seems simple until you think about it”. 4 rules can create a computer so complex it can run itself over and over and over again...

There is so much to the game of life. For example, there are patterns that don't change from one generation to the next–Conway called these still lifes, things like the four celled block, the six celled beehive or the eighth celled pond.

Patterns that needed lots of generations to stabilize are called methuselahs. A good example of a methuselah is the acorn, developed by Charles Corderman, which takes 5,206 generations to stabilize

But this isn't even close to the longest lasting methuselah. On January 16 2021, Dylan Chen discovered one that takes 52, 513 generations to stabilize, which was found using apgsearch (ash pattern generator search) which generates soups (random initial patterns), where ash is a stable oscillation or flying outcome of a soup.

Different patterns in the game have different classifications and names, for example spaceships are finite patterns that return to the initial state after a certain number of generations but in a different location.

The classes for patterns are as follows:

- Class I-still lifes

- Class II-oscillators

- Class III- space ships

- Class IV- guns

- Class V- unstable, predictable patterns

- Class VI-unstable, unpredictable patterns

Here's a neat table (Courtesy of Alan Zucconi):

Gliders are the smallest space ships known to exist–first discovered in 1969 by Richard guy. Then in 1970, Bill Gosper invented the Gosper glider gun, An oscillator that, every 30 generations, spawns a new glider. That was the first Class IV object to be discovered.

Another interesting aspect of the game is the Garden of Eden Theorem. The theorem was proved by Edward Moore and John Myhill in the 1960s– before Conway's Game of life was even invented. Gardens of Eden are patterns that have no predecessors, which can be pretty easily found since you can use the rules of the game to retrace past generations, and therefore must be starting conditions. The Garden of Eden theorem states that the class of surjective (every pattern is mapped to by some other pattern) cellular automata and those which are injective (no two distinct finite patterns map into the same finite pattern) over finite configurations coincide. So any cellular automaton contains Gardens of Eden if and only if it is not surjective.

Basically, a cellular automaton has a Garden of Eden if and only if it has two different finite configurations that evolve into the same configuration in one step.



The point of all this is that simple rules have high sensitivity to initial conditions, ranging from complete annihilation to a static universe to pure chaos. Stephen Wolfram called the game “the purest example I know of the dynamics of collective human innovation.”

Brian Eno said of the game “Complexity arises from simplicity! That is such a revelation; we are used to the idea that anything complex must arise out of something more complex. Human brains design airplanes, not the other way around. Life shows us complex virtual “organisms” arising out of the interaction of a few simple rule”

I would also like to make it abundantly clear I'm not one of those wackos who thinks Conway's game of life is a genuine reflection of our universe, or that it proves the existence of god. Yes, I have actually heard BYU math students say that the game's dependence on starting conditions proves the existence of god. Obviously the rules are very different from the universal laws we have, and most importantly there's no conservation laws, so something could arise from nothing.

Conway's game of life is just an interesting example of mathematical chaos, because it is not readily predictable, but it is NOT random. There are patterns, laws, and emergent phenomena. Kind of like our universe, a few universal laws and a handful of particles, started by an unknown starting conditions 13.8 billion years ago… and now I can write a blog post distributed to the world wide web on a 10” by 13” screen!

Langton's Ant!

Tuesday, January 14th, 4:08PM

I have been on a big cellular automata kick recently. Mostly because I think the patterns they make are pretty, but also because the math behind some of the papers are really interesting. If you haven't played Conway's Game of life or langton's ant I would highly recommend checking them out. Langton's ant is one of my favorites because it is really simple but it is a turing complete machine, technically, despite only having two rules:

1. If the ant is on a white square: The ant turns 90 degrees right, flips the square to black, and moves forward one step.

2. If the ant is on a black square: The ant turns 90 degrees left, flips the square to white, and moves forward one step.

Here's a quick simulation of it I made in javascript–.if you let it run for long enough without refreshing the page, you should see a pattern emerge.

Langton's ant has three main stages–simplicity, where it has simple, symmetric moves, then it has chaos, where it traces a pretty random and irregular path, and then from the chaos stage it creates the last stage, emergent order, a recurrent highway pof repeatable steps that it gets locked into. I'm sure someone much more poetic than me could make that into a metaphor for life or love or something.

I thought these types of games are fun, so I decided to make my own game except with shapes. I call it Silly Billy Polygon Game.

The rules are as follows:

A grid of cells has one of the following initial states in each cell:

1. Empty (no polygon)

2.Square

3. Triangle

4. Hexagon

And will abide by the following growth rules:

1. Empty cells turn into Squares if surrounded by two or more Squares.

2. Squares can grow into Triangles if adjacent to more than two Squares or other Triangles.

3. Triangles can evolve into Hexagons if surrounded by triangles and squares.

4. Hexagons remain Hexagons unless surrounded by another specific combination of shapes that triggers a new, even larger polygon.

Heres a simulation of it (also made with js):

Another cellular automata that ti think is arguable y more interesting than langton's ant is patersons worm. I'm not going to make a simulation for it because it involves an isometric grid and to be honest I have no idea how to code one of those. But Tomasso Marziu made a great simulation of it that I will link here

.

Basically the rules of the game are as follows:

Starting:

Start with an empty, isometric grid

Make a line segment connecting the origin to any other next to it.

There are 6 cardinal directions:

0, which is straight ahead

1, which is a 60° right turn

2, which is a 120° right turn

3 which is a 180° turn (NOT ALLOWED)

4, which is a 120° left turn

5, which is a 60° left turn

You cannot retrace an already occupied path, which is why option 3 is not allowed after any path is made.

So, 0 recurring over and over would make a straight line (BO-RINGG); 1 recurring over and over would make a hexagon; 2 recurring over and over would make a triangle You can stack the rules on top of each other (like 5, 0, 1, 2, 5 or something) to create the rules (in order) that the worm will have to follow