Cellular Automata and Computing
A Computer Architecture final project by Nate Karst, Mike Siripong and Zach Brock

final report [.pdf]
our final report
code we used [.zip]
the python code we used
works cited
list of sources we used
useful links we found





  what this project is about
The goal of this project was to investigate and summarize the many ways in which cellular automata can deepen our understanding of the world around us. Our general focus was on systems that cellular automata can model easily and effectively. However we also found links in the other direction, where cellular automata like systems in nature had inspired and influenced computing. The project was broken up into five parts: Flocking, Epidemiology, Crystal Formation, Genetic Algorithms & Evolvable Hardware and Pattern Formation. Summaries of each of the sections can be seen below. Download our final paper to read the sections in full.

Flocking occurs when a group of animals, without any explicit leadership or guidance, begin to exhibit behavior that appears directed and controlled. This traveling in high-density packs and a common direction can actually be shown to be due to a few simple rules that individuals in the group follow. In fact, for birds or fish effective models have been created that follow just three simple rules. These are:
1. Collision Avoidance: Steer to avoid obstacles and crowding local flockmates
2. Alignment: Steer towards the average heading of local flockmates
3. Cohesion: Steer to move toward the average position of local flockmates
Flocking is thus a perfect example of emergence in cellular automata. If we treat each individual bird or fish as a single CA controlled by these three simple rules, we are able to generate complex naturalistic behavior that closely models nature.
Rule 1: Collision AvoidanceRule 2: Alignment
Rule 3: Cohesion 

Cellular automata are also extremely useful for modeling disease transmission. By treating each cell as an individual and defining a few key constants we can model how much damage a given disease can be expected to do. The four key quantities are the infectivity (the rate at which the disease spreads), latency, (how long before it becomes active in the host), duration (how long it remains in the host and mortality (the percentage of people the disease kills). Below you can see an example of one such simulation. The code used to generate this image is available via our code link.

  crystal formation
Crystal formation is an interesting application of cellular automata because it behaves very similarly to a CA. Each individual particle in the crystal is essentially a cell behaving according to the way its near neighbors behave. The networks used to model formation are also interesting in that they often do not take the traditional arrangement of rectangular cells. For instance, while diamonds would fall under the traditional rectangular domain, water crystals are best modeled by a hexagonal arrangement. The ways in which crystalline structures grow is directly dependent on both the lattice on which it will grow and the rule set governing the addition of new cells to the crystal. In fact, the rules to generate ice crystals are very simple. Below is an example of a hexagonal CA with the rule "if a single neighbor is black, turn black". This simple set of conditions gives us snowflakes.

  genetic algorithms and evolvable hardware
An application in which biology has inspired computing is Genetic Algorithms. A Genetic Algorithm is essentially forced evolution of a solution to a problem. The basic operation of a GA is to take a sample population of solutions, evaluate their performance (or ”fitness”), select pairs of high-ranking members to reproduce (via ”crossover”) and then apply random mutations. One recent and really exciting application of this is Evolvable Hardware, or the application of GAs to hardware problems. This has been made possible by Field-Programmable Gate Arrays. FPGAs are interesting because they provide essentially a hardware representation of cellular automata. Each logic cell in an FPGA is laid out in a grid and connected to four neighbors. By defining a data structure that can indicate the links between each cell it becomes possible to do evolvable hardware. The first example of this was a tone-discriminator, which was evolved to give a different output for a 10kHz input signal than a 1kHz input signal. The circuit that evolved after 5000 generations was able to complete this task but went about it in a bizarre way. Since there was no external clock, the solution that evolved operated in continuous time. In addition it exploited interactions on the molecular level between different parts of the physical substrate the FPGA was printed on. It is still not entirely understood how the circuit works, but the final logic cell wiring of it can be seen below. The grey boxes are cells that were not directly connected to the circuit, but any attempt to suppress them degraded the performance of the system to varying degrees.

  pattern formation
Patterns show up often in nature, from the coloration of fur on a leopard to the shape a fern takes as it grows. The way in which these patterns for is poorly understood. However, Stephen Wolfram has theorized that they are generated in a manner similar to cellular automata. In this model, each pigmentation cell behaves according to the state each of its immediate neighbors has taken on, much same way a cellular automata works. Another example of this is in the way mollusk shells are generated. Since the shell is extruded one cell layer at a time (much like your fingernails), the complex color patterns may be acting as a one-dimensional cellular automata. Examples of mollusk shells can be seen below.

Design © 2004, Adam Particka.