Ponderings on Cellular Automata

General rambling about 0 player games.

Return

Introduction to Cellular Automata

Basics

A cellular automata is a collection of discrete units which can be in any number of given states. This collection is then transformed by iteratively applying an algorithm to every unit which changes it's state based on it's current conditions and the conditions of the units surrounding it

In simple (and less general) terms: A grid of a set number of colors which you repeatedly apply a filter to. The most well known example of a cellular automata is Conways GOL which is made up of an infinite grid of squares which are either alive or dead. These squares (called "cells") follow these rules:

  1. If an alive cell has 0 or 1 living neighbors, it dies by underpopulation
  2. If an alive cell has 2 or 3 living neighbors, it survives
  3. If an alive cell has 4 or more living neighbors, it dies by overpopulation
  4. If a dead cell has exactly 3 living neighbors, it becomes alive

Arising complexity

When the rules of GOL are followed, very complex behavior can arise from these simple rules. Some patterns stay static, some oscillate between some number of states, some patterns grow infinitely and some do not, some translate their position across the board or rotate other shapes.

Conway's GOL is Turing Complete

Turing completeness

A system is turing complete if it can perform any calculation that a computer can. A turing machine is the most simplistic computer possible, made up of an infinite reel of 0's and 1's. A "head" is moved over this reel, this head can read from and write to the reel following some program. Any operation that a modern computer can perform, a turing machine can perform, only slower.

It is relatively simple to prove that GOL is turing complete. We can use a shape called a "Glider" to form wires, and combine these streams with carefully placed "Glider Guns" which endlessly produce gliders to simulate a NOT gate and an AND gate. With these two gates, we can form a NAND gate, from which we can construct every component a computer is made up of. If we combine this with some other shapes which change the direction of gliders and allow two streams to cross, we have every tool we need to create a simple computer. (If you want more details on this, see here)

This sort of arising complexity from simple rules is a staple of cellular automata.