
[ Home ]	[ Software ]	[ Curriculum ]	[ Hardware ]	[ Community ]	[ News ]	[ Publications ]	[ Search ]

Pyro Module CA

This module is designed to allow you to to explore Cellular Automata using Python code and the Pyrobot library.

1D Cellular Automata

Cellular Automata (CA) were invented by John von Neumann as a discrete model of a simplified universe (see Wikipedia.org for a full history and definition). A CA is a matrix of cells, each in a particular state, K, and an associated set of rules that transform the cells over time. Common CAs come in 1D and 2D (Game of Life) variations. For this module, we will explore the simplest, 1D CA.

A 1D CA consists of a row of "cells", each in a state, K. To keep things very simple, we will consider K = 2 and use 0 and 1 to represent the two states. Here is a sample 1D CA (which we will call a lattice):

00010101000101010010101010101001010101001010010

We will consider each cell to have two direct neighbors, one on the left and one on the right. The first and last cells will be defined to have each other as neighbors. In this way, the CA wraps around, and has no beginning nor end.

Now, this wouldn't be very interesting if the CA just sat there. So, we will define a set of "rules" that describe how to change a cell's state. CA rules define a transformation function. Each rule describes what state to transform a single cell into on the following time step.

We could define a simple rule set like so:

Rule Cell   Output
     ----   ------
  A    0      1
  B    1      0

This defines a ruleset with 2 rules. The first rule (A) says that if a cell has a zero in it, then change it to a 1. The second rule (B) says that if a cell has a 0 in it, change it to a 0. We can then apply these rules to the initial lattice:

00010101000101010010101010101001010101001010010

We apply the appropriate rule to each cell to get:

11101010111010101101010101010110101010110101101

All of the 1's became 0's, and 0's became 1's. Likewise, if we apply the ruleset to this new lattice, we get:

00010101000101010010101010101001010101001010010

which is the original lattice. You might say that we are "in a loop" because we are back where we started. Because there is nothing random in this system, we will continue in this cycle, getting back to where we started every other step. If we apply the rules repeatedly, and put the resulting lattices directly under the previous lattice, we get something that looks like:

00010101000101010010101010101001010101001010010
11101010111010101101010101010110101010110101101
00010101000101010010101010101001010101001010010
11101010111010101101010101010110101010110101101
00010101000101010010101010101001010101001010010
11101010111010101101010101010110101010110101101
00010101000101010010101010101001010101001010010
11101010111010101101010101010110101010110101101
00010101000101010010101010101001010101001010010
11101010111010101101010101010110101010110101101
00010101000101010010101010101001010101001010010
11101010111010101101010101010110101010110101101

This is a history view of the 1D CA with time going down, row by row. But this isn't very interesting. It is completely predictable. You could tell me what row 12,125,557 would look like. We can still ask some questions about this simple system:

How many different rulesets are there?
Are all of the resulting lattices of the different rulesets as simple as this one?
Can you predict what will happen in all cases?
How does the size of all possible output rows relate to all possible output rows that you can actually get to by applying the rules? Are they the same?
Given a particular output row, can you work backwards to determine what state led to it? If you could, you might describe the CA as reversible.

A Bigger Neighborhood

Let's consider some larger rulesets, this time taking into account a cell's immediate neighbors. Consider:

Rule Left   Cell   Right      Output
     ----   ----   -----      ------
  0    0     0       0          1
  1    0     0       1          0
  2    0     1       0          0
  3    0     1       1          1
  4    1     0       0          0
  5    1     0       1          1
  6    1     1       0          0
  7    1     1       1          1

This table of 8 rules describes a set of inputs to match (Left, Cell, and Right) and the resulting outputs. To see how to apply these rules, consider the following cellular matrix:

Position:  0  1  2  3  4  5  6
          ---------------------
States:    0  0  1  0  1  1  1

Let's consider the cell at position 3. To see what the state of position 3 at the next time step will be, we consider the state at position 3, and the cells immediately to the Left and Right. In this case, that would be cells at positions 2, 3, and 4. Specifically, that would be the states {1, 0, 1}. We next find the rule in the table that matches that input, and we see that it matches rule #5. The output of rule #5 is 1, so on the next time step that cell will become 1.

In order to compute the values for the ends of the matrix, we will consider the cells to wrap around so that the left-most cell will have the right-most cell as its immediate left. Likewise, the right-most cell will consider the left-most cell to be its immediate right.

We then apply rules for each position, performing the match in parallel. Therefore, after one step, we would have:

Position:  0  1  2  3  4  5  6
          ---------------------
 Time 0    0  0  1  0  1  1  1
 Time 1    0  0  0  1  1  1  0

We can make a couple of observations at this point. Do you see a relationship between the matching input pattern and the rule number?

Sidebar: Binary Numbers

Binary, like decimal, has places. In decimal we use:

1,000s 100s  10's  1's
------ ----  ----  ---
  3     0      4    9

which tells us that 3049 is equal to 3000 + 40 + 9.

Likewise, in binary we us:

64's  32's  16's   8's  4's  2's  1's
----  ----  ----  ---- ---- ---- ----
  1     0     1     0    0    1    0

Therefore, the binary number 1010010 is equal to (in decimal) 64 + 16 + 2 = 82.

How many different rulesets are there for this system?
How does the size of all possible output rows relate to all possible output rows that you can actually get to by applying the rules? Are they the same?
Given a particular output row, can you reverse the CA (work backwards) to determine what state led to it?

Rule numbers

You will notice that the matching pattern is just the rule number, in binary digits. For example, {1, 0, 1} is 5 in binary.

How many rows does the rule table have? You'll notice that it is 2 raised to the 3rd power (2 ^ 3 = 2 * 2 * 2 =8). In general, it will be K (number of states) raised to the 2r + 1 power, where r is the neighborhood radius around the center cell. In our case, r = 1 so 2r + 1 = 3, and there are 8 rows in the table. How many rows would there be in a table where K = 5 and r = 3?

One can also ask how many different rule sets are there for a given table size? Because each output can be one of K states, the total number of rules is K raised to the K raised to the 2r + 1. Where K = 2 and r = 1, we have a total number of 2 ** (2 ** 3) = 256 different rule sets in the simple example of radius = 1.

As a shorthand, we can actually refer to an entire ruleset by referring to its output column. For example, ruleset #110 is just 110 in binary which is 01101110. Ruleset #0 is 00000000, and ruleset #255 is 11111111. We will take the leftmost binary digit to be the most-significant, and so we will match it left-to-right as bottom-to-top. Therefore, ruleset #110 is:

Rule Left   Cell   Right      Output
     ----   ----   -----      ------
  0    0     0       0          0
  1    0     0       1          1
  2    0     1       0          1
  3    0     1       1          1
  4    1     0       0          0
  5    1     0       1          1
  6    1     1       0          1
  7    1     1       1          0

Notice that the output column is (from bottom to top) 01101110 which is 110 in decimal.

This is a nice representation because the decimal number 110 represents the entire table! Draw the entire table for rule 54.

The CA Python library

To explore 1D CA's, we will be using the language Python. You don't need to know the language for now, and you will be able to run the commands as shown.

First, you will need to be sitting in front of one of the computers in Park 231. You will log into Linux, and will be able to run the following examples. First, you must open a "terminal" by selecting "Applications" -> "System tools" -> "Terminal".

To use the code interactively, try (don't type in the % nor the >>> as those represent the prompts):

% python
>>> from pyrobot.general.ca import *
>>> rules = Rules(radius=1)
>>> rules.init(110)

rules.data returns [[0, 1, 1, 0, 1, 1, 1, 0]]. You can also see it by:

>>> rules.display()
  0 .XX.XXX. 0.62

In this output, zero is represented by a dot, and one by an X. The first zero indicates the row (not meaningful for rules), and the last floating-point number (0.62 in this case) is the percent of ones in the rule.

Next, we create a matrix for creating a series of transformations. We will call these histories of 1D rows a lattice:

>>> lat = Lattice(size=65)
>>> rules.watch(lat)

You can set particular 1's and 0's:

>>> lat = Lattice()
>>> lat.init("0" * lat.size)
>>> lat.data[0][lat.size / 2] = 1

The last line will set the middle cell to a state of 1.

Rules have the following keywords and defaults:

Parameter Default Value

radius 3

values (K) 2

bias 0.5

Bias is a value for determining what percentage of the rules should be randomly set to 1's. You can also initialize the rules by giving a specific string, or a ruleset number:

>>> rules = Rules(radius = 1)
>>> rules.init(110)              # equivalent to rules.init("01101110")
>>> rules.data

Lattice has the following keywords and defaults:

Parameter Default Value

size 149

height 150

bias 0.5

You can see the lattice by doing either of the following:

>>> lat.display()   # OR
>>> rules.watch(lat)

Other methods to try:

>>> lat.randomize( .7)  # randomizes to about 70% 1's
>>> rules.randomize(.1)  # randomizes to about 10% 1's

Problems to try:

If you shift the initial conditions to the left or right (and wrap), what is the difference in the resulting behavior?
Try seeing what the effect of making the size of the lattice very small is, but keeping the rule and initial conditions the same.
In what way can this be seen as computing?
Keep the initial condition the same, but try all 256 rules on it, where K = 2, r = 1. What patterns do you see?
Imagine K = 2, r = 3. What is the size of the table? How many different rulesets are there? How can you find some interesting ones?
What can be said of rulesets that are inverses of each other (such as, "1001" and "0110")?
How would the behavior of a CA change if the states were just probabilistically likely, rather than deterministic? Or if there was a mutuation rate that randomly flipped a bit?
How could you make the CA more continuous?
How could you add "conservation" to the CA (ie, so that there is always the same number of ones)?
Explore "reversable" CAs.

Pyro Modules Table of Contents

Pyro - Back to Pyro main page
Beyond Legos - NSF grant that pays for Pyro

Modules

Additional Resources

Reference: PyroSiteNotes

[ Home ]	[ Software ]	[ Curriculum ]	[ Hardware ]	[ Community ]	[ News ]	[ Publications ]	[ Search ]
View Wiki Source \| Edit Wiki Source \| Mail Webmaster