A cellular automaton is really nothing more than an array or a transitive graph of identical finite state machines (aka DFAs), feeding on themselves! (Or, if you want to add randomness, you also add randomness to your machines.)

The possible states of each cell are the states of its finite state machine. At every time step, each cell receives as input the states of its neighbours (there are a finite number of neighbours, and each can be in one of a finite number of states, so this input comes from a finite alphabet). The combination of the cell's current state and its input (a finite amount of information) yields the cell's state in the next time step.

For instance, Conway's Game of Life consists of a 2D array of cells. Each cell has 2 possible states (dead or alive). There are 8 neighbours for each cell, so the input is from an alphabet of size 28=256, giving the states of all cells. Of course the transition function is particularly simple: A dead cell turns alive if it has exactly 3 live neighbours, i.e. it receives one of the 56 possible inputs with exactly 3 1's. A live cell stays alive if it has exactly 2 or 3 live neighbours, i.e. it receives either one of these 56 inputs or one of the 28 inputs with exactly 2 1's.

Note that a Turing machine can easily be modeled in this fashion, essentially by arraying machines along the number line Z. Each machine either represents a tape cell or a tape cell occupied by the Turing machine's head. The rules of the Turing machine are easily adapted to the rules for the 1D cellular automaton. So it's not too surprising that Conway found a cellular automaton (Life) capable of computing any computable function; the surprise is that it's such a simple automaton!

Log in or register to write something here or to contact authors.