A cellular automaton is a simulation based on the turing machine, where each iteration/round, each cell reacts based on its state and the state of the surrounding cells. It represents the basic logic of pattern development based on an algorithm. The rules vary and the grid and cells themselves can be of varying arrangement (grid - 1D, 2D...; cells - square, hexagon...)
Famous, behaves similarly to a simple biological life.
Rules: We have a 2D grid of cells. Each cell can only be alive or dead. Each cell considers its nearest eight cells its neighbors. The game runs in rounds. Each round, every cell counts its neighbors' states and sets its state for the next round. If 2-3 of its neighbors are alive, it will be alive, otherwise dead.
Certain patterns and shapes that develop in interesting ways have gained their own names and categories. Categories: still life (persists but doesn't move, e.g. block), oscillators (periodically changes in place, e.g. blinker), space ships (moves in direction, e.g. glider)
# # ## ## ## # ## # # # # # ### ## # ## ## ## glider block blinker beehive mirrored table
Virtual Ant (vant) simulates the behavior of an ant on a 2D grid according to the following rules: The ant is placed on the grid. Each cell is either black or white. The ant can face north, west, south or east and operates in steps. Each step, it turns the block it is on to its opposite color, and moves 1 step, left if the block it was on was black, right if it was white.
After a round, each cell reacts based on its two surrounding cells, based on a truth table. This table/rules create complex patterns, the system is turing complete. Its simplicity gives possibility to interesting implementations, such as a completely mechanical rule 110 computer. It is called rule 110 because if all the 'result' numbers are added (01101110), it results to 110 in decimal. There are "flipped" versions of rule 110, e.g. rule 137 (inversion of 110) and rule 124 (horizontal reflection of 110).
left / center / right | center next |
---|---|
0/0/0 | 0 |
0/0/1 | 1 |
0/1/0 | 1 |
0/1/1 | 0 |
1/0/0 | 1 |
1/0/1 | 1 |
1/1/0 | 1 |
1/1/1 | 0 |
Nondeterministic, includes random behavior.
Lattice gas automata (LGCA) is a cellular automaton that simulates flowing of fluids. Each gas particle has a velocity.
C implementations: Game of life, Virtual ant, Rule110