More Playing, Less Programming

In this entry we will explore the wonderful world of the Cellular Automaton (CA). Our entry into this world will be provided by the program Cafun. Cafun is written in Java and will run on any system that has a current Java Runtime Environment (JRE). I have run it on Linux and Windows. The screen shots you will see later in the entry are from the Windows environment. I encourage you to download and run the program, exploring as many of the samples that they provide before going further. I'll wait for you.

One of the classic CAs that is included with Cafun is Conway's Game of Life, we will focus on Life as the basis for one of our custom rule sets.

What is a Cellular Automaton?
As someone whose connection with mathematics is as a "recreational mathematician" I will provide my own understanding for what a CA is. For more complete and precise explanations you look to Wiki-pedia and to this introductory article.

A Cellular Automaton is a "discrete state system". What does that mean? It means that the CA system is made up of discrete units (cells) and it tracks the what state the cell is in over time. The state that the cell is in is governed by two components, it's current state and the states of its neighbors. The great John Von Neumann invented the CA concept and used a neighborhood consisting of the four cells that are directly above, below, left and right of the cell being checked. More often the neighborhood used is the Moore neighborhood named for Edward F Moore. This neighborhood consists of the eight cells that surround the current cell. This is what Conway used for his Game of Life (GoL). It is also the default neighborhood for Cafun . GoL was made famous by the late Martin Gardner in and article in Scientific American in October of 1970.

The second part of building a CA are the rules. The "Life rules" set out by Conway are very simple:

1. Cells have two states, on and off
2. If a cell is on and it is surrounded by 2 or 3 other on cells it will remain on
3. If a cell is off and is surrounded by exactly 3 other on cells it will turn on
4. In all other cases a cell that is on will turn off and a cell that is off will stay off.

These very simple rules were originally modeled on a Go board (19x19 grid) with Go stones and on graph paper. Programs that implement the GoL rules have been popular as exercises in computer programming for a long time.

Conway's Game of Life
Let's examine the GoL rules in Cafun . Load up CAFun and open the Simulation "Conway's Game of Life" from the "Classic" folder of included simulations. Do NOT open the default universe when prompted. We're going to look at one of the classic examples of taking a simple pattern and watching it turn into something more complex. Zoom the view to 800% of normal (400% might work if you are using a lower resolution screen). Draw a small + in the middle of the field. (see screenshot)

Using the step (single green arrow) control step through 6 "generations".  You should end up with 4 lines of 3 cells each arranged like a square missing it's corners. From this stage onward you will alternate between this pattern and the pattern you get when you press the step button once more. The lines rotate 90 degrees. The single line is called a "blinker", this pattern of lines is known as "traffic lights". It is one of the many "meta-stable" structures that GoL creates.  To see an actual stable structure arise use the Fill tool and fill the screen with Dead cells. Use the pencil tool and create a pattern of four cells that looks like the L shaped piece in Tetris. (A 3 cell line with one cell off the end to one side. It doesn't matter where you place the one cell.) Click the single step button 4 times. The resulting shape is a hexagon that is stable. All of the Alive cells have 2 neighbors so they don't die. You can continue to put in simple shapes and see what happens. If you just want to create a random pattern select the paint brush tool. Right click on the field and select Stroke Size - 10 Cells and Stroke Intensity - Low. You may want to Zoom out before you do this. Make some strokes on the screen. Then press the "Go" button (the double arrow) and watch what happens. If you leave it on normal speed it will move pretty fast. There is a Simulation Speed setting on the Utilities menu. You may want to set that to "Slow Motion" to get a better view.

Wireworld
Another of the CAs in the Classic folder of Cafun is Wireworld. The link takes you to Karl Scherer's definitive site on this CA that was created by Brian Silverman and featured in Scientific American by A. K. Dewdney in January 1990.

Wireworld has 4 cell types. Here are the types and their transition rules:

• Background: Background cells never change
• Wire: Wire cells will change into Electron Head cells when adjacent to 1 or 2 Electron Heads.
• Electron Head: An Electron Head always turns into an Electron Tail
• Electron Tail: An Electron Tail always turns into Wire

Cafun has a simulation file for Wireworld in the file named "Dewdney's Wire World". But before we can use it we need to correct an error in the rules. Using your favorite text editor (Notepad works in Windows) open the file "Dewdney's Wire World.xml" that is found in the simulations/classic directory in the Cafun directory. (Note: If you are using Notepad on Windows make sure to switch the open dialog to All Files from Text Files.) Look for the section that looks like this:

<cell-type color="192 192 192" id="Wire">
  <mutation cell-type="Electron-Head" priority="top">
    <condition cell-type="Electron-Head" min="1" max="1" />
  </mutation>
</cell-type>

This allows us to look at how Cafun defines its simulations. Cafun takes an object oriented approach to Cellular Automata. Each cell is an instance of a cell type. The rules are defined as mutations that can be considered methods of the type. For now we simply want to change the condition element so that the property max is equal to 2. So  change the condition line to look like this:

  <condition cell-type="Electron-Head" min="1" max="2" />

Save the file and return to CAFun. 

From the simulation menu select "Open Simulation" and select "Dewdney's Wire World". Again ignore the default universe. If you are continuing the same session from our experiments with GoL then you'll want to fill the field with Background cells.

Zoom back to 800% and use the pencil tool (make sure you have stroke size set to 1 and stroke intensity is set to high) to draw out the pattern in the next screenshot:

The loop at the left end of the wire serves as a pulse generator. To lengthen the distance between the pulses increase the size of the loop by adding wire cells to the parallel lines. For now simply run the simulation forward clicking the step control 4 or 5 times. You'll see the red and blue "pulse" split when it reaches the wire with new heads going down the wire and around the loop. This is what allows the loop to continue to pump out new pulses.

The interesting thing about Wireworld is that it provides the ability to model all kinds of electronic devices.  The Scherer site has a wealth of examples. We'll look at a simple example next. One of the simplest electronic components is the diode. We can simulate a diode in Wireworld with the pattern shown in the next screenshot:

In the middle of the wire add two wire cells above and below the line of the main wire. This creates a 3x2 rectangle. In the middle row of the rectangle make the right cell background creating what looks like a C in the middle of the wire. If you run the simulation you will see that the pulses with pass through this pattern.

Change the state of the cells in the middle row making the left cell background and the right cell wire. This has the effect of turning the diode around. Run the simulation again and you will see that the pulses that come up to the diode stop at the diode. This pattern blocks the pulses because the far end of the wire is connected to a side that will always have 3 electron heads if it has any and that does not create a new head on the wire. I encourage you to experiment with creating some of the other patterns that Scherer has on his site to play with Wireworld.

Next time

I have an extended version of the GoL rules that adds some color and a way to start with a random population that I will publish in then next entry and make available for download via Google Docs. The randomization idea comes from some BASIC programs in the book Exploring the Geometry of Nature by Edward Rietman. We'll use this file to explore the various aspects of a Cafun simulation file.

Come to the June 8th TCPC general meeting where Alice and Cafun will be part of the Software Showcase.