- tags
- Unconventional computing, Cellular automata
- resources
- (Mitchell 2005; Wolfram 2002)

Cellular automata are computational models capable of interesting emergent behavior. A major challenge is to understand which CA rules are doing useful or efficient computations. It is not clear how these systems could be programmed or made to compute a particular function.

## Hand-engineered CA rules

Below images show CA rules that can compute non trivial functions (Images are from (Wolfram 2002), see A new kind of science online ). These examples are nice but likely challenging to produce for complex computations.

**Binary adder CA rule**

**Square CA rule**

**Prime CA rule** (sieve of Eratosthenes)

### Hyperbolic space

A cellular automaton can solve the 3-SAT problem in polynomial time on a pentagrid — grids of pentagons — in hyperbolic space (Margenstern 1999).

## Evolution of CA rules

CA rules can also be evolved with Genetic algorithms to perform a particular type of computation. Because it uses a genetic algorithm, this method requires a clear reward/objective function to be effective, which might not be achievable for complex functions were input/output pairs aren’t enough of a signal for finding a solution. (Packard 1988; Mitchell, Crutchfield, and Das 1997)

## Bibliography

Margenstern, Maurice. 1999. “A Polynomial
Solution for 3-SAT in the Space of Cellular Automata in the
Hyperbolic Plane.” *J. UCS* 5 (9):563–73.

Mitchell, Melanie. 2005. “Computation in
Cellular Automata: A Selected Review.” In *Non-Standard
Computation*, 95–140. Weinheim, FRG: Wiley-VCH Verlag GmbH &
Co. KGaA.

Mitchell, Melanie, James P Crutchfield,
and Rajarshi Das. 1997. “Evolving Cellular Automata to Perform
Computations.” In *Handbook of Evolutionary Computation*,
edited by Thomas Bdbendck, David B Fogel, and Zbigniew Michalewicz.
IOP Publishing Ltd.

Packard, Norman H. 1988. “Adaptation
Toward the Edge of Chaos.” *Dynamic Patterns in Complex
Systems* 212. World Scientific:293.

Wolfram, Stephen. 2002. *A New Kind of
Science*. Champaign, IL: Wolfram Media.