Computing in cellular automata

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.


← Back to Notes