A CellularAutomaton, also known as WireWorld. It was described by AlexanderKeewatinDewdney in a ScientificAmerican "Computer Recreations" column.
It allows one to simulate digital logic, using solitary "bits" travelling down "wires" and through "gates".
Needless to say, it supports TuringComplete computation.
Cells are arranged in a square grid, each with 8 neighbors. Each cell has 4 states:
- Background. Always transitions to Background.
- Head. Always transitions to Tail.
- Tail. Always transitions to Wire.
- Wire. transitions to Wire, unless it has 1 or 2 neighbors in state Head, in which case it transitions to Head.
For example, imagine a field with all cells set to Background except for a line of Wire cells, with a Head and Tail at one end. (This pair is called an "electron".) Thus:
tH.........................
The next states will be:
.tH........................
..tH.......................
...tH......................
If the wire forms a loop, the electron will go round and round. If a wire strand leads off the loop, the electron will split and send pulses down the wire. If 2 pulses arrive at the same time in the same place, they can be arranged to cancel. You can make diodes, latches, AND and OR gates.
A diode, if memory serves, is:
..
..tH.. ....
..
See it at http://neekatave.com/ca/examples/wirewrld/index.shtml.
There's a brief article at http://mathworld.wolfram.com/WireWorld.html with some examples of logic gates and an 8x8 -> 16 multiplier.