UserPreferences

PyroModuleCA:Computation

1. PyroModuleCA:Computation

This module is designed to explore the notion of computing with Cellular Automata using the Python Pyrobot library.

1.1. Ideas, Concepts, and Terms

  1. Lattice #1 - if we number lattices the same way we number rulesets, Lattice #1 has one bit on (usually in the center).

  2. [WWW]Garden of Eden Pattern - a pattern that is impossible to get to from a previous state.

  3. Reversible CA - A CA is said to be reversible if for every lattice produced there is exactly one previous lattice.

  4. Totalistic CA - the output bit is determined by a sum of the neighbors. This can be seen as similar to a population encoding in neurons.

  5. Halting Problem - given an arbitrary program with arbitrary input, it is impossible to say whether or not the program will stop or run forever.

  6. Langton's lambda - Langton defined lambda to be the precentage of 1's in a ruleset's output.

1.2. Wolfram's Classes

In 1984, Wolfram defined the following qualitative descriptions of CA's:

  1. Class I. evolves to fixed, homogeneous state (limit points)

  2. Class II. evolves to simple, separated, periodic structures (limit cycles)

  3. Class III. evolves to chaotic, aperiodic structures (chaotic, strange attractors)

  4. Class IV. evolves to complex patterns localized structures (long transients)

http://www.theory.org/complexity/cdpt/html/img101.png

1.3. Can you determine what class a ruleset will fall into?

Langton proposed that there is a correlation between a ruleset's lambda and the class of the ruleset's resulting behavior.

Langton's [WWW]Edge of chaos idea.

1.4. Questions: Part 1

  1. What rule number describes the following rule set? 

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          1
  7    1     1       1          0

  1. Draw the rule table for ruleset #128. What ruleset is the exact inverse of this ruleset? (ie, What ruleset is exactly the same, except that zeros are ones and ones are zero?) Do these two rulesets behave the same on an lattice #1? On a random lattice?

  2. What effect does changing the width of the lattice have on running a ruleset on an initial lattice? Why?

  3. What effect does changing the height have on running a ruleset on an initial lattice? Why?

  4. If you shift the initial lattice to the left or right (and wrap), what is the difference in the resulting behavior?

  5. Imagine K = 3, r = 3. What is the size of the table? How many different rulesets are there?

  6. Try rule #30 on a wide lattice with the string '00001000111000' somewhere near the middle. What is the resulting behavior?

1.5. Questions: Part 2

  1. Define random. Can a CA exhibit random behavior? Explain the why you could, and could not describe a CA as having random behavior.

  2. In what way can 1D CA be seen as computing?

  3. How would the behavior of a CA change if the states were just probabilistically likely, rather than deterministic?

  4. Can you find a ruleset that computes the density classification task? Use radius = 3, to give you a large set of rules to explore.

  5. How does your ruleset compare to GKL? 

import sys
from pyrobot.general.ca import *
rules = Rules()
data = Lattice()

def pause():
    print "---Press ENTER to continue---",
    sys.stdin.readline()

rules.init(gkl)
print "GKL Rule set:"
rules.display()
pause()

for percent in [ x/10.0 for x in range(10)]:
    data.randomize(percent)
    print "GKL Rule applied to a %d%% Lattice, Width = %d:" % (percent * 100, data.size)
    #print rules.applyAll(data)
    #data.display()
    rules.watch(data)
    pause()

1.6. Questions: Part 3

  1. Get familiar with Python (see, for example, http://pyrorobotics.org/?page=PyroModulePythonIntro)

  2. Copy the program /usr/lib/python2.4/site-packages/pyrobot/general/ca.py: 

cp /usr/lib/python2.4/site-packages/pyrobot/general/ca.py myca.py

  1. Alter your version of the code so that you can explore the statistical properties of which rules are "firing" and how often. For example: 

>>> import myca
>>> rules = Rules(radius=1)
>>> lat = Lattice()
>>> rules.watch(lat)
>>> rules.displayStats() # this could be your code

Rule  Fired   Percent
0       12      7.5%
1       34     21.3%
2       76     47.8%
3        0      0.0%
4        9      5.6%
5       16     10.0%
6       12      7.5%
7        0      0.0%